Number Theory: An Introduction to Mathematics

84 II Divisibility

Proposition 1Any a,b∈Nhave a greatest common divisor(a,b).

Proof Without loss of generality we may supposea ≥ b.Ifbdividesa,then

(a,b)=b. Assume that there exists a paira,bwithout greatest common divisor and

choose one for whichais a minimum. Then 1<b<a,sincebdoes not dividea.

Since also 1≤a−b<a, the paira−b,bhas a greatest common divisord.Since

any common divisor ofaandbdividesa−b, and sinceddivides(a−b)+b=a,it

follows thatdis a greatest common divisor ofaandb. But this is a contradiction. 


The proof of Proposition 1 uses not only the multiplicative structure of the setN,

but also its ordering and additive structure. To see that there is a reason for this, con-

sider the setSof all positive integers of the form 4k+1. The setSis closed under

multiplication, since

( 4 j+ 1 )( 4 k+ 1 )= 4 ( 4 jk+j+k)+ 1 ,

and we can define divisibility and greatest common divisors inSby simply replacing

NbySin our previous definitions. However, although the elements 693 and 189 ofS

have the common divisors 9 and 21, they have no greatest common divisor according

to this definition.

In the following discussion we use the result of Proposition 1, but make no further

appeal to either addition or order.

For anya,b∈Nwe say thathis acommon multipleofaandbifa|handb|h.

We say that a common multiplehofaandbis aleast common multipleifhdivides

every common multiple ofaandb. The least common multiple ofaandbis uniquely

determined, if it exists, and will be denoted by [a,b].

It is evident that, for everya,

(a, 1 )= 1 , [a,1]=a,

(a,a)=a=[a,a].

Proposition 2Any a,b∈Nhave a least common multiple[a,b]. Moreover,

(a,b)[a,b]=ab.

Furthermore, for all a,b,c∈N,

(ac,bc)=(a,b)c, [ac,bc]=[a,b]c,

([a,b],[a,c])=[a,(b,c)], [(a,b),(a,c)]=(a,[b,c]).

Proof We show first that(ac,bc)=(a,b)c.Putd=(a,b). Clearlycdis a common
divisor ofacandbc,andso(ac,bc)=qcdfor someq∈ N. Thusac=qcda′,
bc=qcdb′for somea′,b′∈N. It follows thata=qda′,b=qdb′. Thusqdis a
common divisor ofaandb. Henceqddividesd, which impliesq=1.
Ifgis any common multiple ofaandb,thenabdividesgaandgb, and henceab
also divides(ga,gb). But, by what we have just proved,
(ga,gb)=(a,b)g=dg.
Henceh:=ab/ddividesg.Sincehis clearly a common multiple ofaandb, it follows
thath=[a,b]. Replacinga,bbyac,bc, we now obtain
[ac,bc]=acbc/(ac,bc)=abc/(a,b)=hc.