Number Theory: An Introduction to Mathematics

88 II Divisibility

Another example, which we will meet in§4 of Chapter VI, is the valuation ringR
of a non-archimedean valued field. In this case, for anya,b∈R, eithera|borb|aand
so (a,b) is eitheraorb.
In the same way that the ringZof integers may be embedded in the fieldQof
rational numbers, any integral domainRmay be embedded in a fieldK, itsfield of
fractions, so that any nonzeroc∈Khas the formc=ab−^1 ,wherea,b∈Rand
b=0. IfRis a GCD domain we can further require(a,b)=1, anda,bare then
uniquely determined apart from a common unit multiple. The field of fractions of the
polynomial ringK[t]isthefieldK(t)ofrational functions.
In our discussion of divisibility so far we have avoided all mention of prime num-
bers. A positive integera=1issaidtobeprimeif 1 andaare its only positive
divisors, and otherwise is said to becomposite.
For example, 2, 3 and 5 are primes, but 4= 2 ×2and6= 2 ×3 are composite.
The significance of the primes is that, as far as multiplication is concerned, they are
the ‘atoms’ and the composite integers are the ‘molecules’. This is made precise in the
following so-calledfundamental theorem of arithmetic:

Proposition 7If a ∈ Nand a = 1 , then a can be represented as a product of
finitely many primes. Moreover, the representation is unique, except for the order of
the factors.

Proof Assume, on the contrary, that some compositea 1 ∈ Nis not a product of
finitely many primes. Sincea 1 is composite, it has a factorizationa 1 =a 2 b 2 ,where
a 2 ,b 2 ∈Nanda 2 ,b 2 =1. At least one ofa 2 ,b 2 must be composite and not a product
of finitely many primes, and we may choose the notation so thata 2 has these proper-
ties. The preceding argument can now be repeated witha 2 in place ofa 1. Proceeding in
this way, we obtain an infinite sequence (ak) of positive integers such thatak+ 1 divides
akandak+ 1 =akfor eachk≥1. But then the sequence(ak)has no least element,
which contradicts Proposition I.3.
Suppose now that

a=p 1 ···pm=q 1 ···qn

are two representations ofaas a product of primes. Then, by Proposition 6, there exist
djk∈N(1≤j≤m, 1 ≤k≤n)such that

pj=

∏n

k= 1

djk, qk=

∏m

j= 1

djk.

Sincep 1 isaprime,wemusthaved 1 k 1 =p 1 for somek 1 ∈{ 1 ,...,n}, and sinceqk 1
is a prime, we must haveqk 1 =d 1 k 1 =p 1. The same argument can now be applied to

a′=

∏

j= 1

pj=

∏

k=k 1

qk.

It follows thatm=nandq 1 ,...,qnis a permutation ofp 1 ,...,pm.