60 CHAPTER 2 Discrete Mathematics
(ii) Ifl′is a positive multiple of bothaandbthenl≤l′.We denote the least common multiple ofaandbby lcm(a,b).Assume thata andbare integers satisfying gcd(a,b) = 1. Then we
say thataandbarerelatively prime. We say that the integerp > 1
isprimeif the only positive divisors ofpare 1 andpitself. Note that
if pis prime and if a is any integer not divisible byp, then clearly p
andaare relatively prime.
Lemma. Assume thata and bare relatively prime integers and that
the integera|bcfor some integerc. Then, in fact, a|c.
Proof. We have that for some integerss, t ∈ Zthat sa+tb = 1.
Thereforesac+tbc=c. Sincea|bc, we havebc=qafor some integer
q, forcing
c=sac+tbc= (sc+tq)awhich says thata|c, as required.
Lemma. Assume thata andb are relatively prime integers, both di-
viding the integerl. Thenab|l.
Proof. We have thatl=bcfor a suitable integerc. Sincea|lwe have
thata|bc; apply the above lemma to conclude thata|c, i.e.,c=arfor
some integerr. Finally,l=bc=barwhich says thatab|l.
Theorem. Given the integersa, b≥ 0 ,lcm(a,b) =
ab
gcd(a,b).
Proof. Let d = gcd(a,b) and setl =
ab
d. Clearly l is a multiple of
bothaandb. Next, ifsandtare integers such thatsa+tb=d, then
s·
a
d
+t·
b
d= 1, proving thata′=
a
dandb′=
b
dare relatively prime.From this we may conclude that at least one of the pairs (d,a′) or (d,b′)
is relatively prime. Assume that gcd(d,a′) = 1 and letd′= gcd(a′,b).