SECTION 2.1 Elementary Number Theory 61
Thend′|a′andd′|band so clearly d′|d. But then d′ divides botha′
andd, forcingd′|gcd(d,a′), i.e., d′ = 1. That is to say,a′ andb are
relatively prime. Therefore ifl′ is any multiple of a and b then l′ is
a multiple of a′ and b; since a′ and b are relatively prime, we have,
by the above lemma, that a′b|l′. In other words, l|l′, proving that
l= lcm(a,b).
Exercises
- Assume that a and b are integers and that d > 0 is an integer
dividing botha andb. Show that if for some integerss, t∈Zwe
haved=sa+tb,d= gcd(a,b). - Assume that a and b are integers and that there exist integers
s, t∈Zsuch thatsa+tb= 1. Show that a andbare relatively
prime. - Find gcd(1900,399), lcm(1900,399). Find an explicit representa-
tion
gcd(1900,399) = 1900s+ 399t, s, t∈Z. - Find gcd(2100,399), lcm(2100,399). Find an explicit representa-
tion
gcd(2100,399) = 2100s+ 399t, s, t∈Z. - Assume thatnis a positive integer and thata, b∈Zwith gcd(a,n) =
gcd(b,n) = 1. Prove that gcd(ab,n) = 1. - Assume thatpis a prime,aandbare integers and thatp|ab. Use
the Euclidean trick to show that eitherp|aorp|b. - Assume thataandbare relatively prime and thata|bcfor some
integerc. Prove thata|c. - Show that for all integersn≥0, 6|n(n+ 1)(2n+ 1).^3
(^3) Of course, this is obvious to those who know the formula:
∑n
k=1
k^2 = n(n+ 1)(2 6 n+ 1).