Proving unique factorization

Finally I’m going to show that some integral domains are in fact unique factorization domains – in fact, PIDs. There are two ways to prove that a Dedekind domain is a PID, a direct one based on something called the Minkowski bound, and an indirect one based on the Euclidean algorithm. The direct method applies in many more cases, and can not only show that a domain is a PID but also that it doesn’t. But it requires some more work, in particular one nagging theorem with a nightmarish proof, so I’m going to stick to the Euclidean algorithm.

A ring R is called Euclidean if there exists a function v from the set of all nonzero elements of R to the set of all positive integers with the following two properties:

1. v(a) <= v(b) whenever b is divisible by a.

2. Given every a and b in R, either a is divisible by b, or we can write a as bq + r with v(r) < v(b).

In fact, only the second property is necessary – given v that satisfies it, we can always construct v’ that satisfies both – but there’s no harm in citing both. In the expression a = bq + r, we call r the remainder of a when divided by b. For example, Z is a Euclidean domain, with v(a) = |a|, the absolute value of a. We can certainly divide integers with remainder, and make sure the remainder has a lower absolute value than the quotient, so property 2 holds.

Every Euclidean domain is a PID. To see why, let I be any ideal of a Euclidean domain. We can choose an element b of I that minimizes v. For example, in (5) in Z, we can choose 5 or -5. Now, if a in I is not divisible by b, then we can write a as bq + r with v(r) < v(b). An ideal is closed under multiplication by any element of the ring, so bq is in I; it’s closed under addition and subtraction, so r = a – bq is in I. But v(r) < v(b), which is impossible since we chose b to minimize v. So in fact a is divisible by b, and I = (b).

When v is a multiplicative function – and the absolute value is multiplicative – we can prove a property that’s equivalent to 2 but is easier to conceptualize. Dividing throughout a = bq + r by b, we get a/b = q + r/b, and v(r/b) = v(r)/v(b) < 1. So given any a/b in the quotient field of R, we can find q in R such that v(a/b – q) = v(r/b) < 1.

With Z, proving that last statement is almost trivial. Certainly, given any rational number a/b, the nearest integer to a/b satisfies v(a/b – q) <= 0.5 < 1.

The same applies to Z[i], only that instead of the absolute value, v is the norm function, v(a + bi) = a^2 + b^2. Given any number a + bi where a and b are rational, we take c to be the nearest integer to a and d to be the nearest integer to b, so that v(a + bi – c – di) = (a – c)^2 + (b – d)^2 <= 0.5 < 1.

I can show the same for Z[SQRT(m)] where m = -2, 2, or 3 with only a slight modification: v(a + bSQRT(m)) = |a^2 – mb^2|. A similar thing applies to Z[(1+SQRT(m))/2] when m is -3, -7, -11, 5, or 13, but the calculation is a little bit more involved. Apart from these 9 different possible values of m, there are exactly 12 more for which it works, but as they get higher, proving that property 2 holds becomes increasingly difficult.