Integral Domains, GCD and UFD

GCD and UFD

Euclid was bang on when he realized the significance of the greatest common divisor, so many centuries ago.

The greatest common divisor of a and b, written gcd(a,b), is g, if g divides a and b, and every element dividing a and b also divides g. We're still using the word "greatest", borrowed from the integers, even though the elements of the ring might not be ordered in any particular way.

The least common multiple of a and b, written lcm(a,b), is l, if a and b divide l, and every other multiple of a and b is a multiple of l.

We will see that gcd implies lcm and lcm implies gcd. Furthermore, gl = ab. Illustrate this with 6 and 10. We have gcd = 2 and lcm = 30, whence 6×10 = 2×30.

Given a, b, and g, let l = ab/g. this is well defined, since g divides either a or b.

Let m be any multiple of a and b, and let h = gcd(l,m).

By the definition of gcd, h divides l, so write hk = l. In other words, hk = ab/g, or hkg = ab.

since a and b divide l and m, a and b both divide h. Divide through by a and get (h/a)kg = b. By symmetry, kg also divides a, hence kg divides g. this makes k a unit, hence h and l are associates. We're abusing the notation a bit, but let's just say h = l. Now h divides m, whence l divides m, and m is indeed a multiple of l, making l the lcm of a and b.

Now for the converse. Given a, b, and l, let g*l = a*b. In other words, ab is a multiple of a and b, it must be gl for some g.

since l/b is well defined, g divides a, and by symmetry g divides b. It is a common divisor, but is it the greatest common divisor?

Let f be some other common factor of a and b.

Let h = lcm(f,g) = gk.

Rewrite gl = ab as hl = kab.

Since a is a multiple of f and g, it is a multiple of h. Divide through by h and get l = kb*(a/h).

Remember that a is a multiple of f and g, hence a multiple of their lcm, or kg. And since k divides a and a divides l, k divides l. Divide through by k and get l/k = b*(a/h). This means b divides l/k. By symmetry, a also divides l/k. since l/k is a multiple of a and b, and l is the least common multiple, l/k is a multiple of l, and k is a unit.

The least common multiple of f and g is gk, or g, hence f divides g. This makes g the greatest common divisor of a and b.

These operations make sense even for units. If u is a unit, gcd(a,u) = lcm(a,u) = a.

Criteria for a UFD

The following criteria in a factorization domain are equivalent.

  1. The ring is a ufd.

  2. Every irreducible element is prime.

  3. Every two nonzero elements have a gcd.

  4. Every two nonzero elements have an lcm.

  5. The intersection of two principal ideals is another principal ideal.

We already demonstrated 1 ⇔ 2 in the previous section. We showed 3 ⇔ 4 above. Let's show 4 ⇔ 5.

If two principal ideals are generated by a and b, their intersection is the multiples of a and b. If this ideal is principal, generated by l, l divides all multiples, and is lcm(a,b). Conversely, if l is lcm(a,b), l generates the ideal, and the intersection is principal.

Now for 1 → 3. If gt = b, expand everything into prime factors, and the primes in g must be present in b. The same holds for gs = a. So let g be the product of the primes common to a and b, and g becomes the gcd for a and b.

To show 3 → 2, we'll need a couple of lemmas.

Scaling a and b by a constant c scales the gcd. Let g = gcd(a,b) and consider gcd(ca,cb). since cg divides both ca and cb, the gcd is cgk for some k. By definition, cgk divides ca and cb. Thus gk divides a and b. This means gk divides g and k is a unit. Therefore gcd commutes with scaling.

Now for another lemma, gcd is associative. If g is gcd(gcd(a,b),c) then g divides a b and c. If f divides a b and c it divides gcd(a,b) and c, and it divides g. Therefore g is that element that divides a b and c, such that every other factor f dividing a b and c also divides g. It exists, since it is gcd(gcd(a,b),c), and it is unique, since two such elements would divide each other. Now gcd(a,gcd(b,c)) produces the same element, satisfying the same criteria, hence gcd is associative.

Let gcd(p,a) = gcd(p,b) = 1. Start with gcd(p,gcd(p,a)*b) = 1. This is the same as gcd(p,gcd(pb,ab)). employ associativity to rewrite this as gcd(gcd(p,pb),ab). Now gcd(p,pb) = p, so substitute and get gcd(p,ab) = 1.

Let p be any irreducible element. Note that p divides a iff gcd(p,a) ≠ 1. Assume p does not divide a or b, and apply the previous paragraph to show gcd(p,ab) = 1, hence p does not divide ab. Conversely, if p divides ab it divides a or b, hence p is prime. Every irreducible element is prime, giving a ufd.

All five criteria are equivalent.

Since a pid is a factorization domain satisfying principal ideal intersection, it is also a ufd.