The Euclidean algorithm and modular inverses

by David Radcliffe

The greatest common divisor (GCD) of two integers is the largest integer that divides both of the numbers without a remainder. For example, the GCD of 60 and 108 is 12, because 12 is the largest integer that divides both 60 and 108.

The middle-school algorithm for computing the GCD is to list the prime factors of each number, and multiply those factors both numbers have in common.

GCF(60,108) = 12

This method works well when the integers are small, but it can be difficult to find the prime factors when the integers are large. Fortunately, there is a more efficient method for large integers, called the Euclidean algorithm. This algorithm works by subtracting a multiple of the smaller number from the larger number, and repeating until the difference is zero. The last nonzero remainder in this process is the GCD.

Let’s demonstrate this method by computing the GCD of 109 and 299.

299 − 2(109) = 81
109 − 81 = 28
81 − 2(28) = 25
28 − 25 = 3
25 − 8(3) = 1
3 − 3(1) = 0.

The GCD of 109 and 299 is 1, because this is the last nonzero number on the right side. In other words, 109 and 299 are coprime.

Now, finding integer solutions to ax + by = 1 is an especially important problem in number theory. If such a solution (x, y) exists, then we say that x is a modular inverse of a, modulo b. This can also be written as ax ≡ 1 (mod b). It is known that a modular inverse exists precisely when a and b are coprime.

We can compute modular inverses by a simple modification of the Euclidean algorithm. We compute the GCD of a and b as before, except that we apply the procedure to the ordered pairs (0, a) and (1, b) instead of a and b. For example, the procedure for finding the modular inverse of 109 modulo 299 is as follows.

(0, 299) − 2(1, 109) = (−2, 81)
(1, 109) − (−2, 81) = (3, 28)
(−2, 81) − 2(3, 28) = ( −8, 25)
(3, 28) − (−8, 25) = (11, 3)
(−8, 25) − 8(11, 3) = (−96, 1)
x = −96.

Why does this work? Each of the ordered pairs (0, 299) and (1, 109) is a solution to the congruence 109 xy (mod 299), and it’s not too hard to see that if you add a multiple of one solution to another solution, then the result is also a solution. Therefore, the last ordered pair (−96, 1) is a solution to the congruence 109 xy (mod 299).

Once we have found the x-value of an integer solution to 109x + 299y = 1, it is easy to find the corresponding y-value. We simply plug in the value of x that we have found, and solve for y.

109(−96) + 299y = 1
299y = 1 + 109(96) = 10465
y = 10465 / 299 = 35.

Therefore (−96, 35) is an integer solution to 109x + 299y = 1. In fact, the general solution is (−96 + 299k, 35 − 109k) where k is an integer.

Advertisements