THE EUCLIDEAN ALGORITHM

MATH 195

Recall that

(ℤ/nℤ)^{∗} = {a ∈ ℤ/nℤ : gcd(a, n) = 1}

is a group under multiplication. In particular, every element a has an inverse a^{−1}? But how can it be found, if not by luck?

Euclid’s algorithm: Computing the GCD

[This material is covered in §7.5 of the textbook.]

In order to compute the inverse of an element of ℤ/nℤ, first we must check if (ℤ/nℤ)^{∗}, that is, test if gcd(a, n) = 1. Often this is done (when the numbers are small) by calculating the prime factorization of each number: e.g. 8085 = 3·5·7^{2}·11, 7560 = 2^{3} ·3^{3} ·5·7, has gcd(8085, 7560) = 3·5·7 = 105. Indeed, it is enough to know the prime factorization of just one of the numbers; however, when the numbers get large, this method becomes impractical.

There is another algorithm, due to Euclid, as follows:

8085 = 1 · 7560 + 525
7560 = 14 · 525 + 210
525 = 2 · 210 + 105
210 = 2 · 105

The result of this computation is that 105 is the greatest common divisor of 8085 and 7560.

Fact. The probability that two randomly chose integers are coprime equals 6/π^{2} = 0.607927 . . .. That is,

lim_{x→∞} \frac{#\{(a, n) : 0 < a ≤ x, 0 < n ≤ x, gcd(a, n) = 1\}}{x^{2}} = \frac{6}{π^{2}} .

For example, the “random” integers 961 and 733 by the Euclidean algorithm gives us:

961 = 1 · 733 + 288
733 = 3 · 288 + 49
228 = 4 · 49 + 32
49 = 1 · 32 + 17
32 = 1 · 17 + 15
17 = 1 · 15 + 2
15 = 7 · 2 + 1

This is some of the material covered January 31, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

Therefore these integers are indeed coprime!

The Semi-Extended Euclidean Algorithm

We can in fact extend this algorithm to compute the inverse of 733 modulo 961, as follows:

0a ≡ 961 (mod 961)
1a ≡ 733
−(1(1) + 0)a = −a ≡ 228
(3(1) + 1)a = 4a ≡ 49
−(4(4) + 1)a = −17a ≡ 32
(1(17) + 4)a = 21a ≡ 17
−(1(21) + 17)a = −38a ≡ 15
(1(38) + 21)a = 59a ≡ 2
−(7(59) + 38) = −451a ≡ 1 (mod 961)

The numbers 1, 3, 4, 1, 1, 1, 7 are the quotients in the previous calculation (not the remainders).

We write this symbolically as follows: starting with a_{0} = n, a_{1} = a, a_{i+1} the remainder of a_{i−1} upon division by a_{i}, we continue until we reach a_{t} = 0, so we get the decreasing sequence of integers

a_{0} = n > a_{1} > a_{2} > ⋯ > a_{t−1} > a_{t} = 0

and in this case a_{t−1} = gcd(a, n). We would like these numbers to decrease with some speed, so we have an algorithm which is reasonably fast.

Claim. a_{i+1} < a_{i−1}/2.

Proof. If a_{i} ≤ a_{i−1}/2, then a_{i+1} < a_{i} ≤ a_{i−1}/2.

Otherwise, a_{i} > a_{i−1}/2, in which case we substract the number directly, i.e. a_{i+1} = a_{i−1} − a_{i} < a_{i}/2. □

Therefore if we write our numbers in base 2, then the Euclidean algorithm cannot take longer than twice the number of binary digits of our number to complete. Since the binary length differs from the number of decimal digits by the factor log_{2} 10, this algorithm take only essentially only the logarithm of the number (approximately the length of the number) to complete.

What happens in the extended Euclidean algorithm if the numbers are not coprime? Returning to our example of 8085 and 7560, then we obtain

0a ≡ 8085 (mod 8085)
1a ≡ 7560
−1a ≡ 525
15a ≡ 210
−31a ≡ 105
77a ≡ 0 (mod 8085).

Notice the significance of the number 77: it is n/ gcd(a, n) = (3 · 5 · 7^{2} · 11)/(3 · 5 · 7).

THE EUCLIDEAN ALGORITHM 3

The Extended Euclidean Algorithm

We can actually keep track of more, if we want more information. Returning to our example (n = 8085, a = 7560):

1n + 0a = 8085
0n + 1a = 7560
1n − 1a = 525
−14n + 15a = 210
29n − 31a = 105
−72n + 77a = 0.

Notice that 72 = a/ gcd(a, n) = (2^{3} · 3^{3} · 5 · 7)/(3 · 5 · 7). The previous line,

29n − 31a = 105,

is also of some real interest: Fact. If a, n ∈ ℤ, then there are integers x and y such that xn + ya = gcd(a, n).

For the reader with a bit of group theory, translate the statement as: any subgroup of an infinite cyclic group ℤ is cyclic. So, for example, the subgroup ℤa + ℤn ⊂ ℤ must be generated by a single element, namely, gcd(a, n).