Topics in Commutative Rings: Unique Factorisation (2)

In the previous article, we imposed certain finiteness conditions on the ring (specifically a.c.c. on principal ideals: that every increasing sequence of principal ideals is eventually constant), then proved that unique factorisation holds if and only if all irreducible elements are prime.

Let’s run through some standard definitions for gcd and lcm, assuming there’s unique factorisation.

Definition. In a unique factorisation domain, the greatest common divisor (gcd) and lowest common multiple (lcm) of two elements x, y are defined as follows: write

$\begin{aligned}x &= p_1^{m_1} p_2^{m_2} \ldots p_r^{m_r},\\y &= p_1^{n_1} p_2^{n_2} \ldots p_r^{n_r},\end{aligned}$

where the p_i are distinct primes and m_i, n_i ≥ 0. [ If a particular prime does not divide x or y, then just let its exponent be 0 in the expression. ]

The gcd and lcm are defined by:

$\begin{aligned}\gcd(x,y) &= p_1^{\min(m_1, n_1)} \ldots p_r^{\min(m_r, n_r)},\\ \text{lcm}(x,y) &= p_1^{\max(m_1, n_1)} \ldots p_r^{\max(m_r,n_r)}.\end{aligned}$

Note that the gcd and lcm are only well-defined up to associates. E.g. even in Z, we can write gcd(5, -15) = -5 or 5. The gcd and lcm are the unique (up to associate) elements of R which satisfy the following universal properties.

If d|x and d|y, then d|gcd(x, y).
If x|e and y|e, then lcm(x, y)|e.

Principal Ideal Domains

Next, we recall Bezout’s identity: given integers x and y, there exist integers a and b such that ax+by = gcd(x, y).

Is this true in an arbitrary UFD? I.e. for any non-zero x, y, can we always find a, b such that ax+by = gcd(x, y)? Note that this question does not depend on our choice of gcd(x, y) since we can always replace a and b by appropriate associates. Turns out Bezout’s identity fails in general.

Counter-examples for Bezout’s Identity

Let R = Z[x]. It’s a classical result by Gauss that R is a UFD. However, we cannot find integer polynomials a(x), b(x) such that 2·a(x) + x·b(x) = gcd(2, x) = 1.
Let R = R[x, y], which is a UFD. But we cannot find polynomials a(x, y), b(x, y) satisfying x·a(x, y) + y·b(x, y) = gcd(x, y) = 1.

The important property for Bezout’s identity to hold in R is as follows.

Definition. We say R is a principal ideal domain (PID) if every ideal of R is principal.

Theorem. Let R be a principal ideal ring.

R satisfies the a.c.c. on principal ideals.

Every irreducible element of R is prime. [ Together with (1), this means R is a UFD. ]

Furthermore, Bezout’s identity holds in R.

Proof (sketch).

Suppose $\left<a_1\right> \subseteq \left<a_2\right> \subseteq \left<a_3\right> \subseteq \ldots$ . Let I be the union of these sets. In general, union of ideals is not an ideal, but in this case I is (why?). By assumption, it is principal, I = <r>. Since r lies in the union of $\left<a_i\right>$ it must lie in some $\left<a_n\right>$ . Show that $\left<a_n\right> = \left<r\right>$ , and thus all subsequent ideals are also <r>.
Let R be a principal ideal domain and x be irreducible in R. If x divides yz, then consider the ideal <x, y>. This is principal, say <x, y> = <r>. Since x lies in <r>, it is a multiple of r, i.e. x=rs. By irreducibility of x, either r or s is a unit. Prove that if r is a unit then x|z; while if s is a unit, then x|y.
To prove Bezout’s identity, suppose x, y are in R. Then <x, y> is principal, so <x, y> = <r>. We claim that r = gcd(x, y), up to an associate. Indeed:

$d|x, d|y \iff \left<x\right>, \left<y\right> \subseteq \left<d\right> \iff \left<x,y\right> \subseteq \left<d\right> \iff \left<r\right>\subseteq\left<d\right>\iff d|r.$

Since gcd(x, y) lies in <x, y>, there must exist elements a, b of R such that ax+by=gcd(x, y). ♦

(Non)-Examples

In the ring Z[x], the ideal <2, x> is not a principal ideal, so Z[x] is a UFD but not a PID.
In the ring R[x, y], the ideal <x, y> is not a principal ideal, so R[x, y] is a UFD but not a PID.

How do we determine if an integral domain is a principal ideal domain? We’ll answer this in the next section.

Euclidean Domains

Here’s one class of PIDs which are amenable to computations.

Definition. An Euclidean function on an integral domain R is a function $f:R-\{0\}\to\mathbf{N}$ to the set of non-negative integers such that

for any $a,b\in R-\{0\}$ , we can find $q,r\in R$ such that a = bq+r and either r=0 or f(r) < f(b).

Note that q and r do not have to be unique. An Euclidean domain is an integral domain which has an Euclidean function on it.

Theorem. An Euclidean domain is a principal ideal domain.

Proof.

Let $f:R-\{0\}\to \mathbf{N}$ be an Euclidean function. For any non-zero ideal I of R, pick a non-zero element x of I such that f(x) is minimum. We claim I = <x>. Indeed, if y≠0 is in I, we can write y = qx+r, where r=0 or f(r) < f(x). Since r is in I, the second case is impossible by minimality of f(x). So y is a multiple of x and I is principal as desired. ♦

One important class of Euclidean domains is the class of polynomial rings over a field.

Theorem. Let K be a field. Then the ring K[x] of polynomials over K is an Euclidean domain. Hence, it is an principal ideal domain, and in particular a unique factorisation domain.

For the Euclidean function, we take the degree: f(x) → deg(f(x)). Now suppose we have non-zero polynomials a(x) and b(x). We know that we can write:

a(x) = b(x) q(x) + r(x), where r(x)=0 or deg(r) < deg(b).

This is precisely the condition for the Euclidean function.

Exercise. We already saw that Z[x] is not a PID, hence it is not Euclidean either. Explain why the degree function fails to be an Euclidean function.

Summary. So far, we know that:

$\left\{\begin{matrix}\text{Euclidean}\\ \text{domains}\end{matrix}\right\} \subseteq \left\{\begin{matrix}\text{Principal}\\ \text{ideal domains}\end{matrix}\right\} \subseteq \left\{\begin{matrix}\text{Unique factorisation}\\ \text{domains}\end{matrix}\right\}.$

In the next installation, we’ll go through some concrete non-trivial examples of Euclidean domains in algebraic number theory and see their application in elementary number theory.