Number Theory: An Introduction to Mathematics

1 Greatest Common Divisors 89

It should be noted that factorization into primes would not be unique if we admit-
ted 1 as a prime. The fundamental theorem of arithmetic may be reformulated in the
following way: anya∈Ncan be uniquely represented in the form

a=

∏

p

pαp,

wherepruns through the primes and theαpare non-negative integers, only finitely
many of which are nonzero. It is easily seen that ifb∈Nhas the analogous represen-
tation

b=

∏

p

pβp,

thenb|aif and only ifβp≤αpfor allp. It follows that the greatest common divisor
and least common multiple ofaandbhave the representations

(a,b)=

∏

p

pγp, [a,b]=

∏

p

pδp,

where

γp=min{αp,βp},δp=max{αp,βp}.

The fundamental theorem of arithmetic extends at once fromNtoQ: any nonzero
rational numberacan be uniquely represented in the form

a=u

∏

p

pαp,

whereu=±1 is a unit,pruns through the primes and theαpare integers (not neces-
sarily non-negative), only finitely many of which are nonzero.
The following property of primes was already established in Euclid’sElements
(Book VII, Proposition 30):

Proposition 8If p is a prime and p|bc, then p|bor p|c.

Proof Ifpdoes not divideb,wemusthave(p,b)=1. But thenpdividesc,by
Proposition 3(ii).

The property in Proposition 8 actually characterizes primes. For ifais composite,
thena=bc,whereb,c=1. Thusa|bc,buta
banda
c.
We consider finally the extension of these notions to an arbitrary integral domainR.
For any nonzeroa,b∈ R, we say that a divisorbofais aproper divisorifadoes
not divideb(i.e., ifaandbdo not differ only by a unit factor). We say thatp∈Ris
irreducibleifpis neither zero nor a unit and if every proper divisor ofpis a unit. We
say thatp∈Risprimeifpis neither zero nor a unit and ifp|bcimpliesp|borp|c.
By what we have just said, the notions of ‘prime’ and ‘irreducible’ coincide if
R =Z, and the same argument applies ifRis any GCD domain. However, in an
arbitrary integral domainR, although any prime element is irreducible, an irreducible
element need not be prime. (For example, in the integral domainRconsisting of all
complex numbers of the forma+b

√

−5, wherea,b ∈ Z, it may be seen that