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
<br /> \ \mathbb{Z}_{n} <br />
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
<br /> \ \mathbb{Z}_{n} <br />
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.