Number Theory: An Introduction to Mathematics

1 Greatest Common Divisors 87

Proof We show first that ifa=a 1 ···anandd|a,thend=d 1 ···dn,wheredi|ai
( 1 ≤i ≤n). We may suppose thatn >1 and that the assertion holds for prod-
ucts of less thannelements ofN.Puta′ = a 1 ···an− 1 andd′ = (a′,d).Then
d′ =d 1 ···dn− 1 ,wheredi|ai( 1 ≤i <n).Moreovera′′ =a′/d′andd′′=d/d′
are coprime. Sinced′′=d/d′dividesa′′an =a/d′, the greatest common divisor
an=(ana′′,and′′)is divisible byd′′. Thus we can takedn=d′′.
We return now to the proposition. Sincec 1 |

∏

jbj, we can writec^1 =

∏

jdj^1 ,
wheredj 1 |bj.Putb′j=bj/dj 1 .Then

∏

j

b′j=a/c 1 =c 2 ···cn.

Hence we can writec 2 =

∏

jdj^2 ,wheredj^2 |b
′
j. Proceeding in this way, we obtain
factorizationsck=

∏

jdjksuch that

∏

kdjkdividesbj. In fact, since

∏

j,k

djk=a=

∏

j

bj,

we must havebj=

∏

kdjk.

Instead of defining divisibility and greatest common divisors in the setNof all
positive integers, we can define them in the setZof all integers by simply replacing
NbyZin the previous definitions. The properties (i)–(v) at the beginning of this sec-
tion continue to hold, provided that in (iv) we requirec=0 and in (v) we alter the
conclusion tob=±a. We now list some additional properties:

(i)′a| 0 for every a;
(ii)′if 0 |a,then a=0;
(iii)′if c|a and c|b,then c|ax+by for all x,y.

Greatest common divisors and least common multiples still exist, but uniqueness
holds only up to sign. With this understanding, Propositions 2–4 continue to hold, and
so also do Propositions 5 and 6 if we requirea=0. It is evident that, for everya,

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

More generally, we can define divisibility in anyintegral domain, i.e. a commuta-
tive ring in whicha=0andb=0 together implyab=0. The properties (i)–(v) at
the beginning of the section continue to hold, provided that in (iv) we requirec= 0
and in (v) we alter the conclusion tob=ua,whereuis aunit,i.e.u|1. The properties
(i)′–(iii)′above also remain valid.
We d e fi n e aGCD domainto be an integral domain in which any pair of elements
has a greatest common divisor. This implies that any pair of elements also has a least
common multiple. Uniqueness now holds only up to unit multiples. With this under-
standing Propositions 2–6 continue to hold in any GCD domain in the same way as
forZ.
An important example, which we will consider in Section 3, of a GCD domain
other thanZis thepolynomial ring K[t], consisting of all polynomials intwith coef-
ficients from an arbitrary fieldK. The units in this case are the nonzero elements ofK.