SECTION 2.1 Elementary Number Theory 59
given thatd′ divides both a andb, then obviouslyd′ divides the sum
sa+tb=d, i.e.,d′|dalso.
We shall present the following without a formal proof. The interested
reader should to able to trace through the steps.
Theorem. (The Euclidean Algorithm) Let a andb be integers, and
assume thata > 0. Perform the following divisions:
b=q 1 a+r 1 , 0 ≤r 1 < a.Ifr 1 = 0thena|band so, in facta= gcd(a,b). Ifr 1 > 0 , divider 1 into
a:
a=q 2 r 1 +r 2 , 0 ≤r 2 < r 1.Ifr 2 = 0then one shows easily thatr 1 = gcd(a,b). Ifr 2 > 0 , we divide
r 2 intor 1 :
r 1 =q 3 r 2 +r 3 , 0 ≤r 3 < r 2.Ifr 3 = 0, thenr 2 = gcd(a,b). Ifr 3 > 0 , we continue as above, eventu-
ally obtaininggcd(a,b)as the last nonzero remainder in this process.
Furthermore, retracing the steps also gives the “multipliers”s andt
satisfyingsa+tb= gcd(a,b).
Example. To compute gcd(84,342) we can do this by factoring: 84 =
6 ·14 and 342 = 6·57 from which we get gcd(84,342) = 6. However, if
we apply the Euclidean algorithm, one has
342 = 4·84 + 6,
84 = 16·6 + 0.
Therefore, again, 6 = gcd(84,342). However, we immediately see from
the first equation that 6 = 1· 342 − 4 ·84, so we can takes= 1 and
t=−4.
Let a andb be integers. We say that the positive integerl is the
least common multipleofa andb, if
(i)lis a multiple of bothaandb,