Based on the textbook Lagrange's theorem states: The congruence $$f(x) \equiv 0\pmod p$$

in which $$f(x)=a_0x^n+....+a_n,\text{ } a_0\not\equiv0\pmod p$$

has at most $n$ roots. $p$ is a prime number .

Question: Let $f(x)$ be a polynomial of degree $n$, with integral coefficients. Show that if $n+1$ consecutive values of $f(x)$ are divisible by a fixed prime $p$, then $p\mid f(x)$ for every integral $x$.

Approach: We have to consider the cases in which $p\le n+1$ and $p>n+1$

if $p\le n+1$ then the problem is very easy. We can create a complete residue system $\pmod p$ and say for every integer $x$ there exists an integer $y$ in the complete residue system such that $p\mid x-y$ which would lead to the conclusion that $p\mid f(x)-f(y)$ and therefore $p\mid f(x)$.
The problem is when $p>n+1$ and I think we have to use Lagrange's theorem as it's part of the chapter I am reading.
If it's possible, try to use my version of Lagrange's theorem when you solve the problem.


If $p\gt n+1$, then the $n+1$ consecutive values are distinct modulo $p$. Thus $f(x)\equiv 0\pmod{p}$ has at least $n+1$ distinct solutions modulo $p$.

By Lagrange's Theorem, it follows that all the coefficients of $f$ are divisible by $p$. If we look at Lagrange's Theorem exactly as stated, then we can only conclude that $a_0\equiv 0\pmod{p}$. But then the polynomial congruence $f(x)-a_0x^n\equiv 0\pmod{p}$ has too many solutions, so $a_1\equiv 0\pmod{p}$, and so on.

  • $\begingroup$ Ok let's analyze what you say sentence by sentence. In the first sentence you say if $p>n+1$, then $n+1$ consecutive values are distinct modulo p. How is that true?. I think n+1-p integers have to be the same mod p. Nevermind what I said $\endgroup$ – TheMathNoob Jul 4 '16 at 23:27
  • $\begingroup$ @TheMathNoob: Let $a$ and $b$ be two of the $n+1$ consecutive values, where $a\lt b$. Then $0\lt b-a\le n$. Since $p\gt n$, it follows that $p$ cannot divide $b-a$, so $a\not\equiv b\pmod{p}$, meaning that $a$ and $b$ are distinct modulo $p$. $\endgroup$ – André Nicolas Jul 4 '16 at 23:33
  • $\begingroup$ Yes, now why is the following true, "Thus $f(x)\equiv 0(mod$ $ p)$" has at least n+1 distinct solutions modulo p? $\endgroup$ – TheMathNoob Jul 4 '16 at 23:34
  • $\begingroup$ @TheMathNoob: We are told that for consecutive values $x=a,a+1,\dots,a+n$, $p$ divides $f(x)$. So $f(x)\equiv 0\pmod{p}$ holds for (at least) $n+1$ pairwise incongruent values of $x$ modulo $p$. Thus the congruence $f(x)\equiv 0\pmod{p}$ has at least $n+1$ solutions. $\endgroup$ – André Nicolas Jul 4 '16 at 23:39
  • $\begingroup$ how do we conclude $a_0 \equiv 0(mod$ $ p)$ if it's stated in the theorem that it's not. $\endgroup$ – TheMathNoob Jul 4 '16 at 23:42

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.