Gauss: Gauss's Lemma for Polynomials

Today's proof is taken from Carl Friedrich Gauss' Disquisitiones Arithmeticae (Article 42). This is Gauss' classic work on number theory which he wrote when he was 21. It is a masterpiece that includes the first use of modular arithmetic, the first complete proof of the fundamental theorem of algebra, a proof for quadratic reciprocity, Gauss' analysis of cyclotomic equations, as well as the first systematic presentation of number theory.

Lemma 1:

if a prime p doesn't divide an integer a, then (a +bp)/cp is not an integer

Proof:

(1) There exists an integer d such that a ≡ d (mod p) where 1 ≤ d ≤ p-1.

(2) So, p divides a - d. (see here for review of modular arithmetic)

(3) And p divides (a - d) so p divides (a -d) + bp = (a + bp) -d

(4) So therefore a + bp ≡ d (mod p)

(5) So it follows that since p doesn't divide a+bp, then (a +bp)/cp is not an integer.

QED

A monic polynomial is a polynomial whose leading coefficient is 1 (see Definition 5, here)

Theorem 2: Gauss's Lemma for Polynomials

Let P,Q be two monic polynomials such that:

P = x^m + a₁x^m-1 + a₂x^m-2 + a₃x^m-3 + ... + a_m

Q = xⁿ + b₁x^n-1 + b₂x^n-2 + b₃x^n-3 + ... + b_n

If the coefficients of P are rational but not all integers and if the product is also monic such that:

PQ = x^m+n + c₁x^m+n-1 + c₂x^m+n-2 + c₃x^m+n-3 + ... + c_m+n

Then, the coefficients c₁, c₂, ..., c_m+n cannot all be integers.

Proof:

(1) Let us assume that all rational cofficients in a₁, ..., a_m and b₁, ..., b_n are expressed in their lowest form.

(2) Let p be a prime number that divides one of the denominators of P [we can assume this since not all the coefficients of P are integers]

(3) Since Q is monic, it is clear that the at least one of the coefficients of (Q)/p will have p as a factor of its denominator (for example, bⁿ will have (1/p) as its coefficient).

(4) In P, there will always be one term, a fraction, whose denominator involves high powers of p than all the fractional coefficients that precede it and no lower powers than the denominators of all succeeding fractional coefficients.

For example, if there is only one fraction with the rest integers, than this fraction is the coefficient. One can start with the first coefficient divisible by p and then check if there are any coefficients after it that are divisible by a greater power of p.

(5) We can identify the term in step #4 as Gx^g with G divisible by 1/(p^t) with t ≥ 1.

(6) Since p divides at least one of the denominators in (Q)/p, the same term in step #4 exists in (Q)/p.

(7) We can identify the term in step #6 as Hx^h with H divisible by 1/(p^u) with u ≥ 1.

(8) Now, it follows that t + u ≥ 2.

(9) Next, I will show that the term x^g+h in the product of (P) and (Q) will have a fractional coefficient who denominator is divisible by 1/(p^t+u-1). This then will complete the proof since a coefficient that is divisible by 1/(p^t+u-1) where p is a prime is not an integer.

(10) Let the terms in P which precede Gx^g be 'Gx^g+1, ''Gx^g+2 and those which follow Gx^g be G'x^g-1, G''x^g-2

(11) Let the terms in (Q)/p which precede Hx^h be 'Hx^h+1, ''Hx^h+2 and those which follow Hx^h be H'x^h-1, H''x^h-2

(12) If we multiply P and (Q)/p, the coefficient of the term Gx^g*Hx^h is GH + 'GH' + ''GH'' + ... + 'HG' + ''HG'' + ...

(13) Because G,H have the highest power of p, there exists e₀,f₀ such that:

p does not divide e₀
p does not divide f₀

and

GH = e₀/(f₀p^t+u)

(14) Since any of the ('G, ''G, etc.) or ('H, ''H, etc.) have a power of p less than t or u and because any of the (G', G'', etc.) or (H', H'', etc) have a power of p no greater than t or u, it follows that any product of the form ('GH', ''GH'', etc.) will have the following form:

'GH' = e_i/(f_ip^t+u-d_i)

where

p does not divide e_i
p does not divide f_i
d_i ≥ 1.

(15) Now if we sum all the factors in step #14 and reduce the denominator to the lowest term, then we get:

∑ e_i/(f_ip^t+u-d_i) =

= e'/(f'p^t+u-d'i)

where

p does not divide e'
p does not divide f'
d' ≥ 1.

(16) If we add up the result of step #14 with step #15, we get:

(e₀f' + e'f₀p^d)/(f₀f'p^t+u)

where:

p does not divide e₀
p does not divide e'
p does not divide f₀
p does not divide f'
d ≥ 1
(t + u) ≥ 2

(17) Since Q = p*(Q)/p, for this same coefficient for P*Q, we have:

(e₀f' + e'f₀p^d)/(f₀f'p^t+u-1)

where:

p does not divide e₀
p does not divide e'
p does not divide f₀
p does not divide f'
d ≥ 1
(t + u - 1) ≥ 1

(18) Since p does not divide e₀ or f', it follows that p does not divide e₀f.

(19) If:

a = e₀f'
b = ef₀p^d-1
c = f₀f'p^t+u-2

Then we can use Lemma 1 above to conclude that:

(e₀f' + e'f₀p^d)/(f₀f'p^t+u-1)

is not an integer.

QED

Corollary 2.1:

If a monic polynomial in Q[X] divides a monic polynomial with integral coefficients, then its coefficients are all integral.

Proof:

(1) Let f be a monic polynomial with integral coefficients.

(2) Let P be a monic polynomial that divides f.

(3) Since P divides f, there exists a polynomial Q such that:

f = PQ

(4) Since P,f are monic, it follows that Q must also be monic. [See Lemma 1, here]

(5) Assume that the coefficient in P are not all integers.

(6) Then, using Theorem 2 above, it follows that the coefficients of f are not all integers.

(7) But this is not correct since by assumption, all the coefficients of f are integers.

(8) So we reject our assumption in step #5.

QED

References

• Carl Friedrich Gauss, Translated by Arthur A. Clarke, Disquisitiones Arithmeticae, Yale University Press, 1965.