Number Theory: An Introduction to Mathematics

86 II Divisibility

It follows from Proposition 4 that ifcn=ab,where(a,b)=1, thena=dnand
b=enfor somed,e∈N.
The greatest common divisor and least common multiple of any finite set of ele-
ments ofNmay be defined in the same way as for sets of two elements. By induction
we easily obtain:

Proposition 5Any a 1 ,...,an∈Nhave a greatest common divisor(a 1 ,...,an)and
a least common multiple[a 1 ,...,an]. Moreover,

(i)(a 1 ,a 2 ,...,an)=(a 1 ,(a 2 ,...,an)),[a 1 ,a 2 ,...,an]=[a 1 ,[a 2 ,...,an]];
(ii)(a 1 c,...,anc)=(a 1 ,...,an)c,[a 1 c,...,anc]=[a 1 ,...,an]c;
(iii)(a 1 ,...,an)=a/[a/a 1 ,...,a/an],[a 1 ,...,an]=a/(a/a 1 ,...,a/an),where
a=a 1 ···an.

We can use the distributive laws to show that

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

In fact the left side is equal to{a∨(b∧c)}∧(b∨c), whereas the right side is equal to

(b∧c)∨{a∧(b∨c)}={(b∧c)∨a}∧{(b∧c)∨(b∨c)}

={a∨(b∧c)}∧(b∨c).

If

a=(a 1 ,...,am), b=(b 1 ,...,bn),

thenabis the greatest common divisor of all productsajbk,since(ajb 1 ,...,ajbn)=
ajband(a 1 b,...,amb)=ab.
Similarly, if

a=[a 1 ,...,am], b=[b 1 ,...,bn],

thenabis the least common multiple of all productsajbk.
It is easily shown by induction that if(ai,aj)=1for1≤i<j≤m,then

(a 1 ···am,c)=(a 1 ,c)···(am,c),[a 1 ···am,c]=[a 1 ,...,am,c].

Proposition 6If a∈Nhas two factorizations

a=b 1 ···bm=c 1 ···cn,

then these factorizations have a common refinement, i.e. there exist djk∈N( 1 ≤j≤
m, 1 ≤k≤n)such that

bj=

∏n

k= 1

djk, ck=

∏m

j= 1

djk.