Motivation
The integer Euclidean algorithm and polynomial long division have the same structural effect: they reduce a problem to one with a smaller remainder. Earlier chapters used that mechanism separately in integers and in polynomials over a field. We now isolate the hypotheses that make it work, then ask which consequences survive when division with a decreasing remainder is unavailable.
Three classes of domains organize the answer. A Euclidean domain has a division procedure controlled by an integer-valued size. A principal ideal domain asserts that every ideal has one generator. A unique factorization domain asserts that nonzero elements factor into irreducibles with a uniqueness property. These definitions describe different kinds of information. The implications between them need proofs, and a factorization that looks familiar is not evidence that an arbitrary domain belongs to all three classes.
Throughout this chapter, a domain is a commutative ring with identity and no zero divisors. We use the earlier definitions of ideals, units, and polynomial degree. Associate elements differ by multiplication by a unit; factorization uniqueness always allows that ambiguity.
Definitions
Definition 5.1.1
(Three domain conditions)
A Euclidean domain is a domain with a function such that for every with , there exist with and either or . A principal ideal domain, or PID, is a domain in which every ideal is generated by one element. A unique factorization domain, or UFD, is a domain in which every nonzero nonunit has a finite factorization into irreducibles, unique up to order and associates.
Our Euclidean definition requires only the displayed remainder condition. It does not require multiplicativity of the size or an extra comparison between the sizes of an element and its multiples. Integers use , while for a field uses polynomial degree. A field is included: choose constant size zero and always divide with remainder zero.
Definition 5.1.2
(Irreducible and prime elements)
A nonzero nonunit is irreducible if forces at least one of to be a unit. It is prime if forces or . A greatest common divisor of divides both, and every common divisor divides ; it is determined only up to associates.
Every prime element is irreducible in a domain. If , primality gives, say, . Then , and cancellation of nonzero gives , so is a unit. The converse requires additional structure and will be one of the important conclusions for PIDs. Calling an element irreducible because no factorization has been found would prove neither definition.
Concept lensStructural
Divisibility read as containment of principal ideals
In a domain, exactly when ; is a unit exactly when ; and are associates exactly when . In this language a nonzero nonunit is irreducible exactly when is maximal among proper principal ideals, and prime exactly when is a prime ideal. Factorization questions thus become questions about the ordered set of principal ideals. In a PID that set contains every ideal, which is why the chain and maximality arguments below become available.
Theorems
Theorem 5.1.3
(Euclidean division implies principal ideals and Bézout)
Every Euclidean domain is a PID. In a PID, the ideal is generated by a greatest common divisor , and there exist with . In particular, are relatively prime exactly when .
Theorem 5.1.4
(Principal ideals imply unique factorization)
Every PID satisfies the ascending-chain condition on ideals. Every irreducible element of a PID is prime, and every nonzero nonunit factors into irreducibles. Consequently every PID is a UFD, and
Proof sketch or proof idea
Proof
(A least size gives a generator)
Let be a nonzero ideal in a Euclidean domain. The nonempty set of sizes of its nonzero elements has a least value; choose with that value. Divide any by . The remainder is in . If nonzero it would have smaller size, contradicting minimality. Thus every is a multiple of , so . The zero ideal is , completing the PID proof.
In a PID write . Since , divides each. Since , it is an -linear combination of them. Every common divisor divides that combination, so is a greatest common divisor. This argument is valid even when one input is zero; when both are zero the generator is zero, without calling it a unit or an irreducible. A gcd is a divisibility statement, whereas a Bézout identity asserts membership in an ideal. The PID property is what connects the two here.
An ideal chain replaces numerical descent
Proof
(Ascending chains and existence of factorizations)
Suppose is an ascending chain of ideals in a PID. Its union is an ideal: two selected elements lie together in one sufficiently large member of the chain, where sums and scalar multiples are closed. Write . Since , it already belongs to some . Thus , so equality holds and every later ideal is the same. This proves the ascending-chain condition without a Euclidean size function.
Now suppose some nonzero nonunit has no factorization into irreducibles. It is not irreducible, so write with both factors nonunits. At least one factor has no irreducible factorization, or multiplying two finite factorizations would factor ; choose that factor as . Then . Indeed, inclusion follows from divisibility, while equality would give , hence , contradicting that is a nonunit. Repeating would produce a strictly increasing chain of principal ideals. The ascending-chain condition forbids this. Therefore irreducible factorizations exist.
This proof uses the standard set-theoretic setting in which the successive choices can be made. One may equivalently use the ascending-chain condition to choose a maximal principal ideal generated by a counterexample, then factor it and contradict maximality. The obstruction is an infinite chain of strictly larger ideals, not a claim that arbitrary ring elements have decreasing numerical sizes.
Why irreducibles become prime
Proof
(Irreducibles are prime, and uniqueness)
Let be irreducible in a PID and suppose but . The generator of divides , so irreducibility makes either a unit or an associate of . The second possibility would make divide , contrary to assumption. Thus is a unit, and rescaling its Bézout identity gives . Multiply by . Both terms and are divisible by , so . This proves primality.
For uniqueness, compare two irreducible factorizations of a nonzero element. The first factor of one divides the product in the other. Repeated primality makes it divide one of those irreducibles, which is therefore its associate. Cancel the matching nonzero factors and repeat. The finite process leaves only a unit factor. A nonempty product of nonunits cannot be a unit, since if a product has an inverse then each factor does in a commutative ring. Hence the lists have the same length and match up to order and associates. Existence and uniqueness have been established by different arguments, and both are needed for the UFD conclusion.
Proof X-ray
Two different stopping arguments
Euclidean division stops because a nonnegative integer size decreases. The PID factorization argument stops because ideals cannot increase strictly forever. Passing from a Euclidean domain to a PID keeps the second mechanism even when no size function has been specified. Confusing these arguments would silently add a Euclidean assumption to a theorem about all PIDs.
Worked examples
Worked example 5.1.5
(Gaussian division and a gcd certificate)
In , define . For nonzero , choose a Gaussian integer by rounding each real coordinate of to a nearest integer. Then , so the remainder satisfies unless it is zero. Thus the norm is Euclidean.
For and , division gives , followed by . Hence the gcd is a unit and back-substitution yields . Both remainder norms decrease, and the final identity independently certifies relative primality. The Euclidean proof now guarantees principal ideals and unique factorization throughout this ring, rather than only for these two inputs.
Worked example 5.1.6
(A gcd need not generate the two-element ideal)
In , the ideal is proper because every element has zero constant term. If it were , then would divide and . Viewing polynomials in over the domain , a divisor of has degree zero in , so lies in . As a divisor of there, it is a unit or an associate of . The latter cannot divide , as evaluation at shows. Thus every common divisor is a unit, and any proposed generator would be a unit, contradicting properness. The elements have gcd one, but no identity exists in this ring. The Bézout conclusion cannot be transferred to every domain merely from the existence of a gcd.
Worked example 5.1.7
(An irreducible that is not prime)
Let . Its norm is multiplicative, and its only units are . No element has norm two or three: when the norm is at least five, and when it is a square.
The elements two and three have norms four and nine, so any factorization into nonunits would require norm-two or norm-three factors; both are irreducible. Each has norm six, whose nontrivial factorization would require norms two and three, so these elements are irreducible too. Nevertheless
gives inequivalent irreducible factorizations, since their factor norms are different and associates have the same norm. Moreover, two divides the product on the right but neither factor, whose integer coefficient one is odd. Thus irreducible need not imply prime outside the PID argument, and this domain is neither a UFD nor a PID nor Euclidean.
Using the hierarchy without reversing it
To prove a concrete ring is a UFD, it suffices to establish a stronger condition when a convenient proof is available. Gaussian rounding proves Euclidean division, after which the two structural theorems do the remaining work. To disprove that a ring is a PID, however, one must exhibit a nonprincipal ideal or use a valid obstruction such as failure of unique factorization. Failing to find a useful size function is not a proof that the ring is not Euclidean.
The theorem establishes arrows, not equivalence of the definitions. It does not classify all Euclidean functions, prove every UFD principal, or prove a converse implication merely by drawing the same arrow backward. Even an existing algorithm for gcds must be inspected for what it guarantees: calculating a gcd does not automatically express it as a combination, as the polynomial example demonstrates.
Common mistakes
Common mistake
(All three conditions assume a domain)
All three definitions assume a domain. Cancellation of a nonzero factor can fail in a ring with zero divisors, and that failure occurs at essential points in both primality and uniqueness proofs. A Euclidean size is also not required to decrease under every algebraic operation; it is required to decrease for the chosen nonzero remainder.
Counterexample mode
Prime but not irreducible when cancellation fails
Without the domain hypothesis, “prime implies irreducible” is false. In , the class is a nonzero nonunit, and it is prime: residues modulo six have a well-defined parity, and is even exactly when or is. Yet , because , and neither nor is a unit, since all their multiples are even. In the proof that primes are irreducible, now holds with and , but canceling would give : here although . In a domain this cancellation is valid, and the implication holds.
Common mistake
(Irreducible and prime are different conditions)
Irreducible means that every factorization has a unit factor; prime controls divisibility of products. They agree in the domains just proved to be PIDs, but treating them as synonyms in an arbitrary domain would erase the quadratic-integer counterexample. Units and associates must likewise be retained in the uniqueness statement: in , the units are , so a preferred sign alone does not remove every ambiguity.
Summary
A least remainder size forces every ideal to be principal. Principal ideals give Bézout identities and ascending-chain stabilization, which in turn supply prime irreducibles, factorization existence, and uniqueness. Gaussian integers illustrate the successful chain; two-variable polynomials and quadratic integers show which conclusions cannot be inferred from weaker information.
Exercises
Quick check
(Prove that any two gcds of the same pair in a domain are associates, and explain separately what happens for the pair .)
Solution · Answer
Each gcd divides the other. If one is nonzero, write and ; cancellation gives , so the two are associates. For , a gcd must be divisible by every common divisor, including zero; hence it is zero. Both choices are then the same zero element, with no cancellation needed.
Quick check
(In a PID, prove that a nonzero nonunit is prime if and only if is a nonzero prime ideal, and show that an irreducible generates a maximal ideal.)
Solution · Answer
For a nonzero nonunit , the implication or is exactly the prime-element definition, and properness follows because is not a unit. If is irreducible and , then , so is a unit or an associate of . Thus or , proving maximality. The claim excludes units, whose ideal is not proper.
Quick check
(Verify and in . Prove that , , and are irreducible using their norms.)
Solution · Answer
Direct multiplication gives and . The three norms are two, five, five, all positive rational primes. Multiplicativity of the norm forces any factorization to have a norm-one factor, hence a unit. Therefore each element is irreducible. Associates may still differ by any Gaussian unit.
Quick check
(In , prove that the ideal is proper and nonprincipal.)
Solution · Answer
Map to . It is a ring homomorphism because the relation maps to modulo two. Its kernel is precisely the indicated ideal: if is even, write the element as , with even last term. The ideal is therefore proper. If it were , then and , so divides both four and six. Thus it is one or two. Norm two is impossible; norm one makes a unit, contradicting properness. Hence the ideal is nonprincipal.