288 PROPERTIES OF THE INTEGERS [CHAP. 1111.21. Leta=8316 andb=10 920.
(a) Findd=gcd(a, b), the greatest common divisor ofaandb.
(b) Find integersmandnsuch thatd=ma+nb.
(c) Find lcm(a, b), the least common multiple ofaandb.(a) Apply the Euclidean algorithm toaandb. That is, apply the division algorithm toaandband then repeatedly
apply the division algorithm to each quotient and remainder until obtaining a zero remainder. These steps are
pictured in Fig. 11-6(a) using long division and also in Fig. 11-6(b) where the arrows indicate the quotient and
remainder in the next step. The last nonzero remainder is 84. Thus 84=gcd( 8316 ,10 920).Fig. 11-6(b) Now findmandnsuch that 84= 8316 m+ 1092 nby “unraveling” the above steps in the Euclidean algorithm.
Specifically, the first three quotients in Fig. 11-6 yields the equations:( 1 ) 2604 =10 920− 1 ( 8316 ); ( 2 ) 504 = 8316 − 3 ( 2604 ); ( 3 ) 84 = 2604 − 5 ( 504 ).Equation (3) tells us thatd=84 is a linear combination of 2604 and 504. Use (2) to replace 5044 in (3) so 84
can be written as a linear combination of 2604 and 8316 as follows:
( 5 ) 84 = 2604 − 5 [ 8316 − 3 ( 2604 )]= 2604 − 5 ( 8316 )+ 15 ( 2604 )
= 16 ( 2604 )− 5 ( 8316 )Now use (1) to replace 2604 in (5) so 84 can be written as a linear combination of 8316 and 10 290 as follows:( 6 ) 84 = 16 [10 920− 1 ( 8316 )]− 5 ( 8316 )= 16 ( 10920 )− 16 ( 8316 )− 5 ( 8316 )
=− 21 ( 8316 )+ 16 (10 920)This is our desired linear combination. In other words,m=−21 andn=16.
(c) By Theorem 11.16,
lcm(a, b)=
|ab|
gcd(a, b)
=
( 8316 )(10 920)
84
=1 081 08011.22. Find the unique factorization of each number: (a) 135; (b) 1330; (c) 3105; (d)211.
(a) 135= 5 · 27 = 5 · 3 · 3 ·3or135= 33 ·5.
(b) 1330= 2 · 665 = 2 · 5 · 133 = 2 · 5 · 7 ·19.
(c) 3105= 5 · 621 = 5 · 3 · 207 = 5 · 3 · 3 · 69 = 5 · 3 · 3 · 3 ·23, or 3105= 33 · 5 ·23.
(d) None of the primes 2, 3, 5, 7, 11, 13 divides 211; hence 211 cannot be factored, that is, 211 is a prime.
(Remark: We need only test those primes less than√
211.)