Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

272 PROPERTIES OF THE INTEGERS [CHAP. 11

Fig. 11-3

Next we use equation (1) to replace 36 in (4) so we can write 12 as a linear combination of 168 and 540 as follows:

12 = 5 [ 540 − 3 ( 168 )]− 1 ( 168 )= 5 ( 54 )− 15 ( 168 )− 1 ( 168 )= 5 ( 540 )− 16 ( 168 )

This is our desired linear combination. In other words,x=5 andy=−16.

Least Common Multiple

Supposeaandbare nonzero integers. Note that|ab|is a positive common multiple ofaandb. Thus there
exists a smallest positive common multiple ofaandb; it is denoted by

lcm(a, b)

and it is called theleast common multipleofaandb.

EXAMPLE 11.7

(a) lcm(2, 3)=6; lcm(4, 6)=12; lcm(9, 10)=90.

(b) For any positive integera, we have lcm( 1 ,a)=a.

(c) For any primepand any positive integera,

lcm(p, a)=a or lcm(p, a)=ap

according aspdoes or does not dividea.

(d) Supposeaandbare positive integers. Thena|bif and only if lcm(a, b)=b.

The next theorem gives an important relationship between the greatest common divisor and the least common
multiple.

Theorem 11.16: Supposeaandbare nonzero integers. Then

lcm(a,b)=

|ab|

gcd(a, b)