58 CHAPTER 2 Discrete Mathematics
common divisor is typically obtained by factoring the given numbers
into prime factors. However, there is an even more efficient approach,
based on the “Euclidean trick” and on the “Euclidean algorithm.”
Theorem. (The Euclidean Trick)Let a, b∈Z, not both zero. Then
the greatest common divisor d of aand bexists. Furthermore, dhas
the curious representation as
d = sa+tb,for suitable integerssandt.
Proof. Consider the set
S = {xa+yb|x, y∈Zandxa+yb > 0 },and letd be the smallest integer inS(sod >0), and letd=sa+tb.
Since the greatest common divisor of|a|and|b|is clearly the same as
the greatest common divisor of a andb, we may as well just assume
thataandbare both positive. Apply the division algorithm and divide
dinto botha andb:
a=q 1 d+r 1 , b=q 2 d+r 2 , 0 ≤r 1 , r 2 < d.But thenr 1 =a−q 1 d=a−q 1 (sa+tb) = (1−q 1 )a−q 1 tb, we see that if
r 1 >0, thenr 1 ∈S, which is impossible sincer 1 < d, anddwas taken
to be thesmallestelement ofS. Therefore, we must have that r 1 = 0,
which means thatd|a. Similarly,r 2 = 0 and sod|b. Ifd′were another
positive integer which dividesaandb, thena=md′andb=nd′, and
sod = sa+tb =s(md′) +t(nd′) = (sm+tn)d′ which clearly forces
d′|dand sod′≤d.
Notation: We shall denote the greatest common divisor of a andb
by gcd(a,b).
Corollary. If d = gcd(a,b) and if d′ is any integer satisfyingd′|a
andd′|b, then alsod′|d.
Proof. This is easy! There exist integerssandt with sa+tb= d;