The Euclidean Algorithm

Having now shown that Z_n is not a field whenever n is not prime, we want to show Z_p is a field whenever p is prime. To do this, we establish that whenever gcd(a,n)=1 then a has a multiplicative inverse (mod n). Our proof will be by giving an algorithm for constructing the inverse of a. Since our algorithm will require that gcd(a,n)=1, it is not surprising that we should start with the classical algorithm (due to Euclid) for computing gcd(a,n). In this algorithm, you start by dividing n by a (integer division with remainder). You then repeatedly divide the previous divisor by the previous remainder until there is no remainder. The last remainder you divided by is the greatest common divisor. We illustrate the Euclidean algorithm in computing gcd(77,52). 77 ¸ 52 = 1 r 25.
52 ¸ 25 = 2 r 2
25 ¸ 2 = 12 r 1
2 ¸ 1 = 2 r 0
Since the last remainder you divided by is 1, gcd(77,52)=1.

To show this works, we will show that if n ¸ a = q remainder r, then the common divisors of a and n are the same as the common divisors of r and a, and hence the gcd(a,n) = gcd(r,a). Once we establish this, then it will follow that gcd(52,77) = gcd(25,52) = gcd(2,25) = gcd(1,2) = 1. When the last remainder divides the previous divisor evenly, then the last remainder is a divisor both of the previous divisor and of itself. Since no number larger than the last remainder could divide the last remainder, the last remainder must be the greatest common divisor.

Now to establish that if n ¸ a = q remainder r, then the common divisors of a and n are the same as the common divisors of r and a. Suppose d is a common divisor of n and a. Then n = t ´ d for some r and a = s ´ d for some s. We rewrite n ¸ a = q remainder r in multiplicative form as n = q ´ a + r and solve for r to get r = n - q ´ a. Substituting in we get r = (t ´ d) - q ´ (s ´ d) = (t - qs) ´ d so d is also a divisor of r. So any common divisor of a and n is also a common divisor of r and a. On the other hand, suppose d is a common divisor of r and a. Then a = s ´ d for some s and r = u ´ d for some u. Going back to our multiplicative form of the division, we get n = q ´ (s ´ d) + (u ´ d) = (qs + u) ´ d so d is also a divisor of n. So any common divisor of r and a is also a common divisor of a and n and we can conclude the common divisors of a and n and the common divisors of r and a are the same, which implies that gcd(a,n) = gcd(r,a).

Next we see how to adapt this algorithm to finding the inverse of 52 (mod 77). We wish to find an integer b so that 52 ´ b º 1 (mod 77), which means that 52 ´ b = 1 + a ´ 77 for some integer a. Another way to write this is 77 ´ -a + 52 ´ b = 1. Such a sum of multiples of 77 and 52 is called a linear combination of 77 and 52. By reversing the Euclidean algorithm, we can write 1=gcd(77,52) as a linear combination of 77 and 52.

Paradigm:To find the inverse of 52 (mod 77):

Carry out the Euclidean Algorithm. (Note: the inverse only exists if the gcd is 1.)
77 ¸ 52 = 1 r 25
52 ¸ 25 = 2 r 2
25 ¸ 2 = 12 r 1
2 ¸ 1 = 2 r 0
gcd(52,77) = 1
Rewrite the divisions (except the last one) in multiplicative form. (This and the next are often done all at once when you are familiar with the procedure.)
77 = 1 ´ 52 + 25
52 = 2 ´ 25 + 2
25 = 12 ´ 2 + 1
Solve the equalities for the remainder terms.
25 = 77 - 1 ´ 52
2 = 52 - 2 ´ 25
1 = 25 - 12 ´ 2
Substitute the remainders in turn into the equality below (work up the list).
1 = 25 - 12 ´ 2
1 = 25 - 12 ´ (52 - 2 ´ 25)
1 = 25 ´ 25 - 12 ´ 52
1 = 25 ´ (77 - 1 ´ 52) - 12 ´ 52
1 = 25 ´ 77 - 37 ´ 52

The last line is the equation of the form 77 ´ -a + 52 ´ b = 1 that we were looking for, with a = -25 and b = -37. Since this is a moderately long process, you can and should check your work by actually computing 25 ´ 77 - 37 ´ 52 = 1925 - 1924 = 1. The inverse of 52 (mod 77) is then -37, or 40 (= 77 - 37).

The trickiest part about this process is that some numbers are placeholders and should be left alone while other numbers are coefficients and should be computed with. In going from the first line to the third line in step 4, we are going from writing 1 as a linear combination of 2 and 25 to a linear combination of 25 and 52. So we substitute in for 2 in the second line and then collect like terms of 25 and 52. It is important in doing this that we don't actually multiply anything by the 25 or the 52, they are just placeholders. It gets worse when you operate on the third line where there are two 25s, the one on the left a coefficient and the one on the right a placeholder. Some students like to start by underlining all the remainders and keeping them underlined as they go through the computations, but in general you can keep them straight without aids after a little practice. The applet below will work out examples for you so you can practice before attempting the homework. Note the applet will only accept moduli up to 100, so you can't ask it to do your homework for you (oh darn:-)