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 = abq 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/bq) = 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/bq) <= 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 + bicdi) = (ac)^2 + (bd)^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.

11 Responses to Proving unique factorization

  1. Kian says:

    i’ve understood all of the math posts up until this one. is there anyway to explain about the 2nd 1/2 a different way? I don’t get it.

  2. Alon Levy says:

    Do you mean the part beginning in “Every Euclidean domain is a PID”?

  3. Alon Levy says:

    Okay… let me try again. We want to show that I = (b) for some b. Now, for each x in I, we check v(x). Let’s first look at v(x1). If there is no x2 in I such that v(x2) x2), then we let b = x1. If there is such an x2, we repeat the process with x3, etc. This process is bound to terminate at some x(n), because otherwise we’ll eventually get negative values of v, which is impossible. So we have an element b of I that satisfies the condition that for every x in I, v(x) >= v(b).

    Now, we can use property 2 to show that I = (b), where (b) is the ideal of all elements divisible by b. If some x in I is not divisible by b, then we have x = bq + r and v(r) b). On the one hand, xbq is in the ideal; on the other hand, r is not in the ideal. So we have a contradiction, and x is divisible by b.

    I hope it’s more comprehensible…

  4. Katie Kish says:

    Its much more comprehensible – is it possible to show it applied to a problem for me though? (Sorry, I’ve gotten into this habit in logic class too. You can explain something to me a million times, but I always want to see how it’s applicable in a problem set…)

  5. Alon Levy says:

    Well, one problem is proving that the ring Z[i] is a PID, which helps prove that every prime integer that’s equivalent to 1 mod 4 (5, 13, 17, 29, etc.) can be written as the sum of two squares in a unique way.

  6. Katie Kish says:

    Its okay, I got another math genius major to do some with me. You’ve been replaced. 😀 but thanks.

  7. […] First, every algebraic number a has something called a minimal polynomial. There are two ways to define it. First, F[x] is a PID for every field F – in fact, it’s a Euclidean domain, with the Euclidean function being the degree of the polynomial. Since a is algebraic, it’s the root of some nonzero polynomial in Q[x], so the ideal of all polynomials that are 0 at a is generated by some nonzero polynomial, call it m(a)(x). We can multiply m(a) by any constant we like, so we normalize it to be monic. It’s then possible to show that a is in B iff m(a) has integer coefficients. […]

  8. […] For a concrete example, let K = Q(i), O(K) = Z[i]. O(K) is a PID, as I showed ages ago. If p = 1 mod 4, then p = a^2 + b^2 for some integers a and b, so (p) = (a + bi)(a – bi), and we say that p splits; in a more general setting, p splits completely if it factors into ideals that have norm p. If p = 3 mod 4, then N(p) = p^2, so any proper factor will have norm p, which is impossible since it would imply a^2 + b^2 = p; in that case, the ideal (p) is prime so we say p remains prime, or is inert. If p = 2, then (p) = (1 + i)^2 and p is called ramified; in fact (p) = P^n and N(P) = p so P totally ramifies. […]

  9. العاب says:

    I went over this website and I conceive you have a lot of fantastic info , saved to my bookmarks (:.

  10. Thanks for sharing this blog post about the Proving Ring Calibration.
    For more details just visit our website at:

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: