Gauss’ Lemma without Primes

Bruno Haible Mathematisches Institut II Universität Karlsruhe Kaiserstraße 12 D – 76131 Karlsruhe

                     Email: <haible@ma2s2.mathematik.uni-karlsruhe.de>

Started: 3 November 1990 Last change: 19 April 1994

Mathematics Subject Classification: 13A05.

Abstract: We prove a form of Gauss’ lemma which holds in a wider class of rings than the factorial rings.

1. GCD Rings

Definition 1: A GCD ring is an integral domain R such that every two elements a, b ∈ R have a gcd (a, b) (that is, a d ∈ R such that d | a, d | b, (c | a ∧ c | b ⇒ c | d)). Note: Factorial rings are GCD rings. (For if R is factorial and a, b ∈ R \ {0} then ∏_{p} p^{min^{(ord_{p} (a),ord_{p} (b))}} is

a gcd (a, b).)

Note (W. Trinks): Not every GCD ring is factorial. (Put R = ⋃_{n=1}^{∞} k[X^{1/n}] where k is a field.)

In an integral domain, two elements a, b are called associated (or multiplicatively equivalent: a ≈ b) if a | b and b | a. This is an equivalence relation, and a ≈ b ⇔ b ∈ a · R^{×}. See [Ja], section 2.14. From now on, let R be a GCD ring. Lemma 1: Let a, b, c, … in R.

(a) gcd (a, b) is unique up to associates.

(b) gcd (a, b) = 0 iff a = 0 and b = 0.

(c) If a′ | a and b′ | b then gcd (a′, b′) | gcd (a, b).

(d) gcd (a, b + ac) ≈ gcd (a, b).

(e) gcd (ac, bc) ≈ gcd (a, b) · c.

(f) gcd (a, bc) | gcd (a, b) · gcd (a, c).

(g) gcd (a, gcd (b, c)) ≈ gcd (gcd (a, b), c).

(h) gcd is a commutative and associative binary operation on R/R^{×}. To any a_{1}, …, a_{n} ∈ R (n ∈ IN \ {0}) a gcd (a_{1}, …, a_{n}) can be defined; it is invariant under permutation of the a_{i} and is uniquely defined up to associates by the condition

(∀i : d | a_{i}) ∧ ((∀i : c | a_{i}) ⇒ c | d).

(i) If a_{1}, …, a_{n} ∈ R (n ∈ IN \ {0}), then there is a d ∈ R such that a_{1} = d · a_{1}′, …, a_{n} = d · a_{n}′ and gcd (a_{1}′, …, a_{n}′) ≈ 1.

(j) gcd (a, b_{1} + ac_{1}, …, b_{n} + ac_{n}) ≈ gcd (a, b_{1}, …, b_{n}). Proof: (See also [Ja], section 2.14.)

(a) If d and d′ are two gcds of a and b, then d | d′ and d′ | d.

(b) Immediate.

(c) Let d = gcd (a′, b′). Then d | a′ | a and d | b′ | b.

(d) If d | a, then d | b + ac is equivalent to d | b.

(e) By (b), we may assume c ≠ 0. Put d = gcd (a, b) and e = gcd (ac, bc). One easily sees d · c | e. From \frac{e}{c} | a and \frac{e}{c} | b one gets \frac{e}{c} | d, so e | d · c.

(f) Obviously gcd (a, bc) | a | a · gcd (a, c). By (c) and (e), one has gcd (a, bc) | gcd (ab, bc) ≈ b · gcd (a, c). Combine this using (e): gcd (a, bc) | gcd (a · gcd (a, c), b · gcd (a, c)) ≈ gcd (a, b) · gcd (a, c).

(g) Obvious.

(h) Obvious.

(i) Put d = gcd (a_{1}, …, a_{n}). If d = 0, let all a_{i}′ = 1. Else put a_{i}′ = \frac{a_{i}}{d}, and from (e) we get d ≈ d · gcd (a_{1}′, …, a_{n}′).

(j) By (d), we have

gcd (a, b_{1} + ac_{1}, …, b_{n} + ac_{n}) ≈ gcd (a, gcd (a, b_{1} + ac_{1}), …, gcd (a, b_{n} + ac_{n}))
≈ gcd (a, gcd (a, b_{1}), …, gcd (a, b_{n}))
≈ gcd (a, b_{1}, …, b_{n}).

q.e.d.

Proposition 2: Every two elements a, b ∈ R have a lcm (a, b) (that is, an e ∈ R such that a | e, b | e, (a | f ∧ b | f ⇒ e | f)). The lcm (a, b) is uniquely defined up to associates. We have gcd (a, b) · lcm (a, b) ≈ a · b. Proof: Let’s first prove the existence of lcm (a, b). Put d = gcd (a, b). If d = 0, we put e = 0 and are done. If d ≠ 0, put e := \frac{ab}{d} ∈ R. We have a | a · \frac{b}{d} = e and b | \frac{a}{d} · b = e. For any f ∈ R with a | f and b | f, put f′ = gcd (ab, f). We then also have a | f′ and b | f′. If f′ ≠ 0 then consider \frac{ab}{f′} which divides a and b. It follows that e | f′ | f. So e is a lcm (a, b). Uniqueness: If e and e′ are two lcms, then e | e′ and e′ | e. q.e.d. Lemma 3: Let a, b, c, … in R.

(a) lcm (a, b) = 0 iff a = 0 or b = 0.

(b) If a′ | a and b′ | b then lcm (a′, b′) | lcm (a, b).

(c) lcm (ac, bc) ≈ lcm (a, b) · c.

(d) lcm (a_{1}a_{2}, b_{1}b_{2}) | lcm (a_{1}, b_{1}) · lcm (a_{2}, b_{2}).

(e) lcm (a, bc) | lcm (a, b) · lcm (a, c).

(f) lcm (a, lcm (b, c)) ≈ lcm (lcm (a, b), c).

(g) lcm is a commutative and associative binary operation on R/R^{×}. To any a_{1}, …, a_{n} ∈ R (n ∈ IN \ {0}) a lcm (a_{1}, …, a_{n}) can be defined; it is invariant under permutation of the a_{i} and is uniquely defined up to associates by the condition

(∀i : d | a_{i}) ∧ ((∀i : c | a_{i}) ⇒ c | d).

Proof:

(a) Immediate.

(b) Let e = lcm (a, b). Then a′ | a | e and b′ | b | e.

(c) By (a), we may assume c ≠ 0. Put e = lcm (a, b) and f = lcm (ac, bc). One easily sees f | e · c. From a | \frac{f}{c} and b | \frac{f}{c} one gets e | \frac{f}{c}, so e · c | f.

(d) a_{1}a_{2} and b_{1}b_{2} both divide lcm (a_{1}, b_{1}) · lcm (a_{2}, b_{2}).

(e) By (b) and (d), lcm (a, bc) | lcm (aa, bc) | lcm (a, b) · lcm (a, c).

(f) Obvious.

(g) Obvious.

q.e.d.

Lemma 4:

(a) lcm (gcd (a, b), c) ≈ gcd (lcm (a, c), lcm (b, c)).

(b) gcd (lcm (a, b), c) ≈ lcm (gcd (a, c), gcd (b, c)).

Proof:

(a) Put d = gcd (a, b). From d | a we get lcm (d, c) | lcm (a, c), from d | b we get lcm (d, c) | lcm (b, c). Combine both to get lcm (d, c) | gcd (lcm (a, c), lcm (b, c)). For the other direction, write a = d · a′, b = d · b′ with gcd (a′, b′) ≈ 1. Then lcm (a, c) | lcm (a, ca′) ≈ lcm (d, c) · a′ and lcm (b, c) | lcm (b, cb′) ≈ lcm (d, c) · b′. So by Lemma 1(c): gcd (lcm (a, c), lcm (b, c)) | gcd (lcm (d, c) · a′, lcm (d, c) · b′) ≈ lcm (d, c) · gcd (a′, b′) ≈ lcm (d, c).

(b) Write a = d · a′, b = d · b′, c = d · c′ with d = gcd (a, b, c) and gcd (a′, b′, c′) ≈ 1. lcm (a′, b′) | gcd (a′, b′) · lcm (a′, b′) ≈ a′b′ implies gcd (lcm (a′, b′), c′) | gcd (a′b′, c′) | gcd (a′, c′)gcd (b′, c′) ≈ lcm (gcd (a′, c′), gcd (b′, c′)) · gcd (a′, b′, c′) ≈ lcm (gcd (a′, c′), gcd (b′, c′)). Multiplying this by d, we get gcd (lcm (a, b), c) | lcm (gcd (a, c), gcd (b, c)). On the other hand, from a | lcm (a, b) we get gcd (a, c) | gcd (lcm (a, b), c), from b | lcm (a, b) we get gcd (b, c) | gcd (lcm (a, b), c), and this gives lcm (gcd (a, c), gcd (b, c)) | gcd (lcm (a, b), c).

q.e.d.

Corollary 5:

(a) (R/R^{×}, gcd, lcm) is a distributive lattice; the neutral elements for gcd and lcm are 0 · R^{×} and 1 · R^{×}, respectively.

(b) ((R \ {0})/R^{×}, gcd, lcm) is a distributive lattice.

Proof: Obvious from the previous lemmas. q.e.d. Note: Several other statements usually considered “typical for factorial rings” hold in GCD rings, for example:

(i) gcd (a + b, lcm (a, b)) ≈ gcd (a, b). (ii) gcd (a^{m} − 1, a^{n} − 1) ≈ a^{gcd^{(m,n)}} − 1 for m, n ∈ IN. (iii) If a^{n} | b^{n} and n ∈ IN \ {0}, then a | b.

2. Gauss’ Lemma

Let’s continue to assume that R is a GCD ring. Definition 2: The content of a polynomial f(X) = a_{n}X^{n} + ⋯ + a_{0}X^{0} ∈ R[X] is defined as cont (f) := gcd (a_{n}, …, a_{0}) ∈ R/R^{×}. If cont (f) ≈ 1, f is called primitive. Theorem 6: Gauss’ Lemma: For f, g ∈ R[X] we have cont (fg) ≈ cont (f) · cont (g). Proof: Write f = a_{n}X^{n} + ⋯ + a_{0}X^{0}, g = b_{m}X^{m} + ⋯ + b_{0}X^{0} and fg = c_{n+m}X^{n+m} + ⋯ + c_{0}X^{0}. We prove the claim by induction on n + m. If m = 0, then cont (fg) = gcd (a_{n}b_{0}, …, a_{0}b_{0}) ≈ gcd (a_{n}, …, a_{0})b_{0} ≈ cont (f) · cont (g). Similarly for n = 0. Now let m > 0, n > 0. We may assume f and g to be primitive. (Otherwise write f = cont (f) · f̃, g = cont (g) · g̃ with f̃, g̃ being primitive by Lemma 1(i), observe that f̃g̃ will be primitive, and compute cont (fg) = cont (cont (f)cont (g) · f̃g̃) ≈ cont (f)cont (g) · cont (f̃ ; g̃) ≈ cont (f)cont (g).) By Lemma 1(f),

cont (fg) = gcd (c_{n+m}, …, c_{0})
≈ gcd (a_{n}b_{m}, gcd (c_{n+m−1}, …, c_{0}))
| gcd (a_{n}, gcd (c_{n+m−1}, …, c_{0})) · gcd (b_{m}, gcd (c_{n+m−1}, …, c_{0}))

By Lemma 1(j),

gcd (a_{n}, gcd (c_{n+m−1}, …, c_{0})) ≈ gcd (a_{n}, c_{n+m−1}, …, c_{0})
≈ gcd (a_{n}, c_{n+m−1} − a_{n}b_{m−1}, …, c_{n} − a_{n}b_{0}, c_{n−1}, …, c_{0})
≈ gcd (a_{n}, cont ((f − a_{n}X^{n})g))

The induction hypothesis gives cont ((f − a_{n}X^{n})g) ≈ cont (f − a_{n}X^{n})cont (g) ≈ cont (f − a_{n}X^{n}), and we get

gcd (a_{n}, gcd (c_{n+m−1}, …, c_{0})) ≈ gcd (a_{n}, cont ((f − a_{n}X^{n})g)) ≈ gcd (a_{n}, cont (f − a_{n}X^{n}))
≈ cont (f) ≈ 1

Similarly, gcd (b_{m}, gcd (c_{n+m−1}, …, c_{0})) ≈ 1. This proves cont (fg) ≈ 1. q.e.d. Theorem 7: R[X] is a GCD ring. Proof: Let f, g ∈ R[X]. We have to find a gcd d of f and g. If f = 0, put d = g, and we are done. Similarly for g = 0: put d = f. We now assume f ≠ 0, g ≠ 0. Write f = cont (f) · f̃ and g = cont (g) · g̃, with f̃, g̃ being primitive by Lemma 1(i). Let K = Quot (R) the quotient field of R. The Euclidean algorithm produces d̃:= gcd (f̃, g̃) in

K[X], with d̃∈ f̃· K[X] + g̃ · K[X]. We may assume d̃ to lie in R[X] (otherwise multiply d̃ by the common denominator of its coefficients). We may also assume d̃ to be primitive (otherwise divide d̃ by its content). Now put d := gcd (cont (f), cont (g)) · d̃.

We first claim that d̃ is a gcd of f̃ and g̃ in R[X]. First, since d̃ | f̃ in K[X], we can write \frac{_{f}}{_{d}} = \frac{a}{b}k with

a, b ∈ R \ {0} and a primitive k ∈ R[X]. Examining the content of bf̃ = akd̃, one sees a ≈ b, therefore

\frac{_{f}}{_{d}} ∈ R[X]. So, d̃ | f̃ in R[X], and similarly d̃ | g̃ in R[X]. Second, since d̃ ∈ f̃· K[X] + g̃ · K[X], there are

u, v ∈ R[X], c ∈ R \ {0} with c · d̃= u · f̃+ v · g̃. If a polynomial h ∈ R[X] divides both f̃ and g̃, then h | c · d̃ and cont (h) | cont \binom{}{f} ≈ 1. Writing \frac{c_{d}}{h} = \frac{a}{b}k with a, b ∈ R \ \{0\} and a primitive k ∈ R[X] and examining

the content of bcd̃= ahk, one sees bc ≈ a, therefore \frac{_{d}}{h} = \frac{a}{bc}k ≈ k ∈ R[X], and h divides d̃.

We now claim that d is a gcd of f and g in R[X]. It is trivial that d = gcd (cont (f), cont (g))·d̃| cont (f)·f̃ = f and similarly d | g. Now let h ∈ R[X] divide both f and g. Write h = cont (h) · h̃ with a primitive h̃. From h | f it follows that cont (h) | cont (f) and h̃ | f̃. (To see this, write k := \frac{f}{h} = cont (k) · k̃. From f = hk it follows that cont (f) ≈ cont (h)cont (k) and therefore f̃ ≈ \frac{f}{cont (h)cont (k)} = h̃k̃.) Similarly, cont (h) | cont (g)

and h̃ | g̃. We conclude cont (h) | gcd (cont (f), cont (g)), h̃ | d̃ and therefore h | d.

q.e.d.

Corollary 8: R[X_{1}, …, X_{n}] is a GCD ring. Proof: Repeated application of Theorem 7. q.e.d.

3. References

[Ja] Nathan Jacobson: Basic Algebra I. Freeman 1985.