# Proving Gauss' polynomial theorem

Let $P \in \mathbb{Z}[x], P(x) = \displaystyle\sum\limits_{j=0}^n a_j x^j, a_n \neq 0$ and $a_0 \neq 0$; if $p/q$ is a root of P (with p and q coprimes) then $p|a_0$ and $q|a_n$

I've managed to prove the first part ($p|a_0$) and I suppose I'm not far from proving the second, though I'd really like some feedback since I'm just starting with making proofs of my own.

Proof:

$P(x) = a_n(x-p/q)\displaystyle\prod\limits_{j=2}^n (x-r_j)$, with $r_j$ being the other n-1 roots of P(x).

It follows that $a_0 = a_n(-p/q)\displaystyle\prod\limits_{j=2}^n (-r_j)$

Then, $-p/q|a_0$ and obviously $p/q|a_0$. Rephrasing, $a_0 = l\frac{p}{q} = \frac{l}{q} p$ with $l \in \mathbb{Z}$.

This implies $p|a_0$ if $l/q \in \mathbb{Z}$, but this is trivial since $q|lp$ and q and p are coprimes, so $q|l$.

Therefore, $p|a_0$.

As for the second part, we want to see that $q_i|a_n \forall i \leq n$.

We define $d$ as the least common multiple of $\{q_1, q_2,...,q_n\}$. Then, $q_i|a_n \forall i \leq n \iff d|a_n$.

Also, it follows that $d|\displaystyle\prod\limits_{j=1}^n q_j$, so we want to see that $a_n = l \displaystyle\prod\limits_{j=1}^n q_j$ with $l \in \mathbb{Z}$. Here's where I have my doubts with the proof as I have no way to show that l is indeed an integer.

Rearranging the previously given equation for $a_0$:

$a_n = a_0 \displaystyle\prod\limits_{j=1}^n \frac{-q_j}{p_j}$

Using the previous reasoning, as $p_i|a_0 \forall i \leq n$, then $a_0 = k \displaystyle\prod\limits_{j=1}^n p_j$.

Replacing $a_0$:

$a_n = k \displaystyle\prod\limits_{j=1}^n -q_j$, which is equivalent to $q|a_n$ as shown earlier.

-
The proof that $p|a_0$ isn't complete since it assumes without justification that $a_n\ \prod_{j=2}^n(-r_j)\in \mathbb Z$. But one can prove $p|a_0$ the same way as in my answer - see my comment to Mariano. – Bill Dubuque Nov 3 '10 at 5:13
I hadn't seen this attributed to Gauss — it's often called the "rational root test". – Dylan Moreland May 11 '12 at 1:57
@DylanMoreland: Over the last few years I've noticed that a handful of theorems have alternative names here in Latin America (not just my professors, but books, and even Wikipedia, offer this alternative names). This is one example. The intermediate value theorem is called Bolzano's theorem, the rank-nullity theorem is called the 'dimension theorem' and this corollary: en.wikipedia.org/wiki/Fundamental_theorem_of_calculus#Corollary is called Barrow's rule, just to name a few. – F M May 11 '12 at 3:58

Hint $\displaystyle\rm\ \ 0 = q^n\ P(\frac{p}q)\ =\ a_n\ p^n + q \ (\cdots)\ \Rightarrow\ q\:|\: a_n\:p^n\ \Rightarrow\ q\:|\:a_n\$ by Euclid's Lemma.
Note $\$ This result is not usually called Gauss' polynomial theorem but, rather, the Rational Root Test / Theorem. This is a special case of Gauss's Lemma for polynomials. Namely, if $\rm\:\alpha\:$ is an algebraic number with primitive minimal polynomial $\rm\: f(x)\in \mathbb Z[x]\:$ and if $\rm\: g(\alpha) = 0\:$ for $\rm\: g(x)\in \mathbb Z[x]\:$ then by Gauss' Lemma $\rm\ f(x)\:|\:g(x)\ in\ \mathbb Z[x].\:$ Hence the leading coefficient of $\rm\:f\:$ divides the leading coefficient of $\rm\:g,\:$ and ditto for the constant coefficients. The Rational Root Test is just the special case when $\rm\:f\:$ has degree $= 1.\:$ Indeed $\rm\ \alpha = p/q\in \mathbb Q\:$ with $\rm\:(p,q)=1\:$ has primitive minimal polynomial $\rm\: f(x) = q\:x - p\:$. Therefore if $\rm\:g(\alpha) = 0\:$ then the above implies $\rm\ (q\:x-p)\:|\:g\ \ in\ \ \mathbb Z[x]\:$ hence $\rm\:q\:|\:g_n,\ p\:|\:g_0\ \ in\ \ \mathbb Z,\:$ which is precisely the Rational Root Test.
If you know how to prove the first part, just apply it to the polynomial $t^n P(t^{-1})$.
Yes, either implication is a consequence of the other by reversing the polynomial. But usually the opposite direction is clear once one see the direction I gave. Sometimes I post it symmetrically to make this clear: $0 = a_n p^n + pq (\cdots) + a_0 q^n$ implies $p|a_0, q|a_n$. – Bill Dubuque Nov 3 '10 at 3:50