104 6. Integers, Divisors, and Primes
(d) Show that this algorithm, when applied to two 100-digit integers, does not
take more than 1500 iterations.The Euclidean Algorithm gives much more than just the greatest com-
mon divisor of the two numbers. The main observation is that if we carry
out the Euclidean Algorithm to compute the greatest common divisor of
two positive integersaandb, all the numbers we produce during the com-
putation can be written as the sum of an integer multiple ofaand an
integer multiple ofb.
As an example, let’s recall the computation of gcd(300,18):
gcd(300,18) = gcd(12,18) = gcd(12,6) = 6.Here the number 12 was obtained as the remainder of the division 300÷
18; this means that it was obtained by subtracting from 300 the highest
multiple of 18 that is smaller that 300: 12 = 300− 16 ·18. Let’s record it
in this form:
gcd(300,18) = gcd(300− 16 · 18 ,18).
Next, we obtained 6 by subtracting 12 from 18, which we can do so that
we maintain the form of (multiple of 300)+(multiple of 18):
gcd(300− 16 · 18 ,18) = gcd(300− 16 · 18 , 17 · 18 −300).So it follows that the g.c.d. itself, namely 6, is of this form:
6=17· 18 − 300.Let us prove formally that all the numbers produced by the Euclidean
Algorithm for gcd(a, b) can be written as the sum of an integer multiple of
aand an integer multiple ofb. Suppose that this holds for two consecutive
numbers we computed, so that one isa′ =am+bn, and the other is
b′=ak+bl, wherem, n, k, lare integers (not necessarily positive). Then
in the next step we compute (say) the remainder ofb′moduloa′, which is
a′−qb′=(am+bn)−q(ak+bl)=a(m−qk)+b(n−ql),which is of the right form again.
In particular, we get the following:
Theorem 6.6.3Letd= gcd(a, b). Thendcan be written in the form
d=am+bn,wheremandnare integers.
As in the example worked out above, we can maintain the representation
of integers in the formam+bnduring the computation. This shows that the
expression fordin the theorem not only exists, but is easily computable.