90 II Divisibility
6 = 2 × 3 =( 1 +
√
− 5 )( 1 −
√
− 5 )has two essentially distinct factorizations into
irreducibles, and thus none of these irreducibles is prime.)
The proof of Proposition 7 shows that, in an arbitrary integral domainR,every
element which is neither zero nor a unit can be represented as a product of finitely
many irreducible elements if and only if the followingchain conditionis satisfied:
(#)there exists no infinite sequence(an)of elements of R such that an+ 1 is a proper
divisor of anfor every n.
Furthermore, the representation isessentially unique(i.e. unique except for the order
of the factors and for multiplying them by units) if and only ifRis also a GCD domain.
An integral domainRis said to befactorial(or a ‘unique factorization domain’)
if the ‘fundamental theorem of arithmetic’ holds inR, i.e. if every element which is
neither zero nor a unit has such an essentially unique representation as a product of
finitely many irreducibles. By the above remarks, an integral domainRis factorial if
and only if it is a GCD domain satisfying the chain condition (#).
For future use, we define an element of a factorial domain to besquare-freeif it
is neither zero nor a unit and if, in its representation as a product of irreducibles, no
factor is repeated. In particular, a positive integer is square-free if and only if it is a
nonempty product of distinct primes.
2TheBezout Identity ́
Ifa,bare arbitrary integers witha=0, then there exist unique integersq,rsuch that
b=qa+r, 0 ≤r<|a|.In factqais the greatest multiple ofawhich does not exceedb. The integersqandr
are called thequotientandremainderin the ‘division’ ofbbya.
(Fora>0 this was proved in Proposition I.14. It follows that ifaandnare positive
integers, any positive integerbless thananhas a unique representation ‘to the basea’:
b=b 0 +b 1 a+···+bn− 1 an−^1 ,where 0≤bj<afor allj. In factbn− 1 is the quotient in the division ofbbyan−^1 ,
bn− 2 is the quotient in the division of the remainder byan−^2 , and so on.)
Ifa,bare arbitrary integers witha=0, then there exist also integersq,rsuch that
b=qa+r, |r|≤|a|/ 2.In factqais the nearest multiple ofatob. Thusqandrare not uniquely determined
ifbis midway between two consecutive multiples ofa.
Both thesedivision algorithmshave their uses. We will be impartial and merely
use the fact that
b=qa+r, |r|<|a|.Anidealin the commutative ringZof all integers is defined to be a nonempty
subsetJsuch that ifa,b∈Jandx,y∈Z,thenalsoax+by∈J.