# Euclid's Algorithm

1. Mar 31, 2006

### 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.

2. Mar 31, 2006

### HallsofIvy

It's not clear to me what you want. "Explaining" Euclid's algorithm in terms of Zn seem much to complicated to me. Euclid certainly didn't know anything about Zn! 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.