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?

  • 1
    $\begingroup$ 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 :-) $\endgroup$ – 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.

  • $\begingroup$ @AdamHughes I forgot monic, which however was in the hypotheses of the OP. $\endgroup$ – egreg Jun 23 '15 at 21:03
  • $\begingroup$ Yeah, I realized after reading that I had remembered, then forgotten myself. :-) $\endgroup$ – 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


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$.

  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jun 23 '15 at 19:58
  • $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jun 23 '15 at 20:54
  • $\begingroup$ @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. $\endgroup$ – user26486 Jun 23 '15 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.