1 Greatest Common Divisors 85If we putA=([a,b],[a,c]), B=[a,(b,c)],then by what we have already proved,A=(ab/(a,b),ac/(a,c)),
B=a(b,c)/(a,(b,c))=(ab/(a,(b,c)),ac/(a,(b,c))).Since any common divisor ofab/(a,b)andac/(a,c)is also a common divisor of
ab/(a,(b,c))andac/(a,(b,c)), it follows thatAdividesB. On the other hand,a
dividesA,sinceadivides [a,b]and[a,c], and similarly(b,c)dividesA. HenceB
dividesA. ThusB=A.
The remaining statement of the proposition is proved in the same way, with greatest
common divisors and least common multiples interchanged.
The last two statements of Proposition 2 are referred to as the distributive laws,
since if the greatest common divisor and least common multiple ofaandbare
denoted bya∧banda∨brespectively, they take the form(a∨b)∧(a∨c)=a∨(b∧c), (a∧b)∨(a∧c)=a∧(b∨c).Properties (i), (ii) and (v) at the beginning of the section say that divisibility is a
partial orderingof the setNwith 1 as least element. The existence of greatest common
divisors and least common multiples says thatNis alatticewith respect to this partial
ordering. The distributive laws say thatNis actually adistributivelattice.
We s a y t h a ta,b∈Narerelatively prime,orcoprime,if(a,b)=1. Divisibility
properties in this case are much simpler:
Proposition 3For any a,b,c∈Nwith(a,b)= 1 ,
(i)if a|c and b|c, then ab|c;
(ii)if a|bc, then a|c;
(iii)(a,bc)=(a,c);
(iv)if also(a,c)= 1 ,then(a,bc)= 1 ;
(v)(am,bn)= 1 for all m,n≥ 1.
Proof To prove (i), note that [a,b]dividescand [a,b]=ab. To prove (ii), note that
adivides(ac,bc)=(a,b)c=c. To prove (iii), note that any common divisor ofa
andbcdividesc, by (ii). Obviously (iii) implies (iv), and (v) follows by induction.
Proposition 4If a,b∈Nand(a,b)= 1 , then any divisor of ab can be uniquely
expressed in the form de, where d|a and e|b. Conversely, any product of this form is a
divisor of ab.
Proof The proof is based on Proposition 3. Supposecdividesaband putd=(a,c),
e=(b,c).Then(d,e)=1 and hencededividesc.Ifa=da′andc=dc′,then
(a′,c′)=1ande|c′. On the other hand,c′|a′band hencec′|b.Sincee=(b,c),it
follows thatc′=eandc=de.
Supposede= d′e′,whered,d′divideaande,e′divideb.Thend|d′,since
(d,e′)=1, and similarlyd′|d,since(d′,e)=1. Henced′=dande′=e.
The final statement of the proposition is obvious.