# Monic polynomial $= 0 \mod p$ for all $x$

For a monic polynomial with integer coefficients (leading coefficient of $1$) $f(x)$ where $f(x) \equiv 0$ mod $p$ for all $x$, where $p$ is a prime number how do I show that the degree of the polynomial must be greater than $p$? Frankly I don't even understand how such a polynomial is possible. If it's always $0$ for all choices of $x$, then shouldn't all coefficients be $0$? But then how is it monic?

• Probably we are to assume that $p$ is a prime. Otherwise we have counterexamples such as $x(x-1)(x-2)\equiv0\pmod6$ and $x(x-1)(x-2)(x-3)\equiv0\pmod{24}$ for all integers $x$. It is a fair enough assumption that in a number theoretic context $p$ stands for a prime number, so don't take my rambling too seriously! I just felt like showing off the tiniest bit :-) – Jyrki Lahtonen Jun 23 '15 at 20:35

I assume $p$ is prime. Since $F_p=\mathbb{Z}/p\mathbb{Z}$ is a field, a monic (or just nonzero) polynomial over $F_p$ having $p$ distinct roots must have degree at least $p$.

Of course such polynomials exist: $x(x-1)(x-2)\dots(x-p)g(x)$, where $g$ is any monic polynomial.

• @AdamHughes I forgot monic, which however was in the hypotheses of the OP. – egreg Jun 23 '15 at 21:03
• Yeah, I realized after reading that I had remembered, then forgotten myself. :-) – Adam Hughes Jun 23 '15 at 21:53

Well first of all, we see $f(x)$ is not just the zero polynomial, since it is monic. Now consider an integer $n$, since $f(n)\equiv 0\mod p$ for all $n$, that means that $f([n])\equiv 0\mod p$ where $[n]$ is the equivalence class of $n$ mod $p$. Then if we factor $f(x)$ mod $p$ we see that each of the $p$ equivalence classes is a root of the polynomial, hence

$$(x-i)|f(x)\quad \text{for all } 0\le i\le p-1$$

i.e. $r(x)=x(x-1)\ldots (x-(p-1))|f(x)$ since each $x-i, x-j$ are coprime for $i\ne j$. Indeed this is easy to see as

$$(j-i)^{-1}\big((x-i)-(x-j)\big)=1$$

is a linear combination which is equal to $1$--here I'm using the Euclidean algorithm to compute the gcd, and since we're in a domain, we know if $a|c, b|c$ and $\gcd(a,b)=1$ then $ab|c$.

Since the degree of the divisor $x(x-1)\ldots (x-(p-1))$ is $p$, the degree of $f$ is at least $p$ since $f(x)=r(x)s(x)$ for some polynomial $s(x)$ and we have that $\deg(r(x)s(x))=\deg r(x)+\deg s(x)$. Finally, since the degree for non-zero polynomials is always $\ge 0$, we see that $\deg f(x) \ge p+0=p$.

As to your question as to how this is possible, consider $f(x)=x^p-x$, then by Fermat's little theorem, $a^{p}\equiv a\mod p$ for all $a\in\Bbb Z$, so this is a non-zero polynomial, which is still $0$ mod $p$ whenever you plug in any integer value for $x$. The difference is that it's just divisible by $p$, i.e. congruent to $0$ mod $p$ for all integer $x$, even if it's not equal to $0$.

• Counterexample $\$ Over $\,\Bbb Z/8,\$ for $\,f(x)=x^2\!-1\,$ we have that $\,f(3)= 0 = f(1)\,$ so $\,x\!-\!1,\, x\!-\!3\mid x^2\!-1,\,$ but their product $\, (x\!-\!1)(x\!-\!3) = x^2\!-4x+3\,$ does not divide $\,x^2\!-1.\,$ This cannot happen over a domain since the $\,x-i\,$ are prime, so their lcm = product. But you need to explicitly justify that crucial inference. See the Bifactor Theorem for further motivation. – Bill Dubuque Jun 23 '15 at 19:58
• @BillDubuque Thanks for the feedback. I mostly avoided it because of the very basic nature of the problem: it seemed it was from a basic number theory class where they might not discuss it as explicitly, but I found a simple way to talk about the lcm/gcd. – Adam Hughes Jun 23 '15 at 21:58

In below proof I'll use $$a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots+b^{n-1}\right)$$

Theorem: a polynomial of degree $n\ge 1$ has at most $n$ zeroes mod $p$ (prime).

Proof: By induction. $ax- b\equiv 0\pmod{\! p}$ with $a\not\equiv 0$ has exactly one solution. Assume any polynomial of degree $k\ge 1$ has at most $k$ roots mod $p$.

Choose an arbitrary polynomial of $k+1$'th degree $f(x)_{k+1}$. If it has no roots mod $p$, we're done. Otherwise let a root mod $p$ be $x_1$. Then

$$f(x)_{k+1}\equiv f(x)_{k+1}-f(x_1)_{k+1}$$

$$\equiv a_{k+1}\left(x^{k+1}-x_1^{k+1}\right)+a_k\left(x^{k}-x_1^{k}\right)+\cdots+a_1\left(x -x_1\right)+a_0\left(1-1\right)$$

$$\equiv (x-x_1)\left(a_{k+1}\left(x^k+x^{k-1}x_1+\cdots+xx_1^{k-1}+x_1^{k}\right)+a_k\left(x^{k-1}+x^{k-2}x_1+\cdots+x_1^{k-1}\right)+\cdots+a_2\left(x+x_1\right)+a_1\right)$$

$$\equiv (x-x_1)P(x)\pmod{\! p}$$

with $P(x)$ being a polynomial of degree $k$. Thus by Euclid's lemma:

$$f(x)_{k+1}\equiv 0\pmod{\! p}\iff \left(x\equiv x_1\!\!\!\pmod{\! p}\ \ \text{ or }\ \ P(x)\equiv 0\!\!\!\pmod{\! p}\right),$$ so $f(x)_{k+1}\equiv 0\pmod{\! p}$ has at most $k+1$ solutions.

Since in your case $f(x)$ has $p$ zeroes mod $p$, its degree is $\ge p$.

• The proof must use that $\,p\,$ is prime since otherwise their are counterexamples (see my comment to Adam's answer). But the proof doesn't mention the word "prime" anywhere. – Bill Dubuque Jun 23 '15 at 20:54
• @BillDubuque I used it twice, just not explicitly mentioning it. E.g., $ax\equiv b\pmod{\! m},\, a\not\equiv 0\pmod{\! m}$ with composite $m$ may easily have more than one solution, e.g. $2x\equiv 4\pmod{\! 6}$. Also, I implicitly used Euclid's lemma. I've edited the answer. – user26486 Jun 23 '15 at 21:07