# Gauss' Lemma for Monic Polynomials

What is often referred to a Gauss' Lemma is a particular case of the Rational Root Theorem applied to monic polynomials (i.e., polynomials with the leading coefficients equal to 1.):

Every real root of a monic polynomial with integer coefficients is either an integer or irrational.

The proof of the Rational Root Theorem made use in an essential way of two Euclid's propositions (VII.24 and VII.30) that underlie the Fundamental Theorem of Arithmetic (a.k.a. Prime Factorization Theorem). The extent to which the properties of divisibility of integers is important for the proof of Gauss' Lemma or the more general Rational Root Theorem. Richard Beigel proved the Lemma for the polynomials in the form $x^{n}-m$ using Euclid's algorithm but not the Fundamental Theorem of Arithmetic.

An absolutely novel proof of Gauss' Lemma has been published by David Gilat of Tel Aviv University, Israel. The new proof uses neither prime factorization nor divisibility; it does not even require one to know what it means for a number to be prime. It assumes only that the set of natural numbers is well ordered, i.e., that each of its nonempty subsets has a least element.

### Proof

Let $r$ be a real root of the monic polynomial

$P(x) = x^{n}+c_{n-1}x^{n-1}+\ldots +c_{0}$

where $n$ is a positive integer and $c_{0}, \ldots, c_{n-1}$ are integers, and suppose that $r$ is rational but not an integer. Then $r$ is uniquely (and strictly) sandwiched between two consecutive integers, say $q \lt r \lt q + 1$. Since $r$ is rational, so are its first $n-1$ powers, $r^{1},r^{2},\ldots ,r^{n-1}$. Consequently, the set

$M = \{m > 0|\space m,mr,mr^{2},\ldots ,mr^{n-1} \mbox{are integers}\}$

is nonempty. Since $r$ is a root of the polynomial $P(x)$, $r^{n} = -(c_{n-1}r^{n-1} +\ldots + c_{0})$. For every $m \in M$, $m(c_{n-1}r^{n-1} +\ldots + c_{0})$ is an integer, and thus $mr^{n}$ is an integer as well.

We are going to derive a contradiction by showing that $M$ does not have a least element, i.e., for every $m \in M$ there is an $m' \in M$ with $0 \lt m' \lt m$. To this end, let $m \in M$ and set $m'= (r-q)m$. Then for each $i = 0,1,2,\ldots ,n-1$ we have $m'r^{i} = mr^{i}-qmr^{i-1}$ which is an integer, implying $m' \in M$; and $0 \lt m' \lt m$ because $0 \lt r \lt q < 1$. Thus $M$ cannot have a least element. It follows that $r$ must be an integer or irrational.

We can adapt this proof to establishing Rational Root Theorem:

Let $Q(x)$ be a polynomial with integer coefficients, say

$Q(x) = c_{n}x^{n}+c_{n-1}x^{n-1}+\ldots +c_{1}x+c_{0}.$

and suppose that $r = a/b$ is a rational root of $P$ (that is, $P(r)=0$) expressed in lowest terms (so that $a$ and $b$ are relatively prime). Then $a$ divides $c_{0}$ and $b$ divides $c_{n}$.

### Proof

I shall only show the latter part, namely that $b$ divides $c_{n}$. Define

$M = \{m > 0|\space m(c_{n-1}r^{n-1}+\ldots +c_{1}r+c_{0}) \mbox{is integer}\}.$

As before, $M\ne \emptyset$. For $m\in M$, $mc_{n}r^{n}=mc_{n}a^{n}/b^{n}$ is also integral. Now there are two possibilities: either $b$ divides $c_{n}$ or not; in the latter case, it divides $m$. In the first case, we are done. Otherwise, set $m'= (r-q)m$. Then

\begin{align} m'(c_{n-1}r^{n-1}+\ldots +c_{1}r+c_{0}) &= m(r-q)(c_{n-1}r^{n-1}+\ldots +c_{1}r+c_{0}) \\ &= r[m(c_{n-1}r^{n-1}+\ldots +c_{0})]-q[m(c_{n-1}r^{n-1}+\ldots +c_{0})] \end{align}

in which both numbers are integers. As before $m'\in M$ and $m'\lt m$, so that unless $b|c_{n}$ the process will continue indefinitely, implying that $M$ lacks a least element.

## References

1. D. Gilat, Gauss's Lemma and the Irrationality of Roots, Revisited, Math. Mag. 85 (2012) 114-116