Euclid's Algorithm Explained: Modulo n & Remainders

[skook]

I can do it, but can't understand how it works. Is there a straightforward expalnation in terms of
$$\ \mathbb{Z}_{n}$$
the set of remainers in modulo n? Could someone try to explain, pls.

 

[HallsofIvy]

I can do it, but can't understand how it works. Is there a straightforward expalnation in terms of
$$\ \mathbb{Z}_{n}$$
the set of remainers in modulo n? Could someone try to explain, pls.

It's not clear to me what you want. "Explaining" Euclid's algorithm in terms of Z_n seem much to complicated to me. Euclid certainly didn't know anything about Z_n! Euclids algorithm asserts that if m and n are two positive integers, with greatest common divisor p, there exist two integers, a and b, such that am+ bn= p. The "algorithm" itself is a way of finding a and b by successive divisions. For example, if m= 18 and b= 8, then the greatest common divisor is 2. 8 divides into 18 twice, with remainder 2, 2 divides into 8 4 times with remainder 0, showing that 18- 2(8)= 2: a= 1, b= -2.
Second example, the greatest common divisor of 31 and 7 is 1: 7 divides into 31 4 times with remainder 3: 31= (4)(7)+ 3 or 31- 4(7)= 3. 3 divides into 7 twice with remainder 1: 1= 7- 2(3)= 7- 2(31- 4(7))= 8(7)- 2(31).
a= 8, b= -31.

 

[Architeuthis Dux]

Euclid's Algorithm is a mathematical method for finding the greatest common divisor (GCD) of two numbers. This algorithm involves repeatedly dividing the larger number by the smaller number until the remainder is equal to zero. The last non-zero remainder is the GCD of the two numbers.

In terms of modulo n, the algorithm can be explained as follows:

1. Start with two numbers, a and b, and set the remainder r = a % b (where % represents the modulo operator).

2. If r = 0, then b is the GCD of a and b. If r ≠ 0, then continue to step 3.

3. Set a = b and b = r. This means that the larger number is now replaced by the smaller number, and the smaller number is replaced by the remainder.

4. Repeat steps 1-3 until the remainder is equal to zero.

In terms of the set of remainders in modulo n, \mathbb{Z}_{n}, the algorithm can be explained as finding the GCD of two numbers by repeatedly subtracting multiples of n until the remainder is zero. This process is essentially the same as the one described above, but instead of using the modulo operator, we are working with remainders in modulo n.

For example, if we want to find the GCD of 15 and 6 in modulo 10, we can use the following steps:

1. Set r = 15 % 6 = 3.

2. Since r ≠ 0, we continue to step 3.

3. Set 15 = 6*2 + 3. This means that we subtracted 2 multiples of 6 from 15, leaving us with a remainder of 3.

4. We now set a = 6 and b = 3, and repeat the process.

5. Set r = 6 % 3 = 0. Since r = 0, we know that 3 is the GCD of 15 and 6 in modulo 10.

In summary, Euclid's Algorithm in terms of modulo n involves finding the GCD of two numbers by repeatedly subtracting multiples of n until the remainder is zero, and the last non-zero remainder is the GCD. This can be seen as a more efficient way of finding the GCD, as it reduces the number of steps needed compared to other methods.