# Proof about Lagrange's theorem in number theory

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.
• 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 – TheMathNoob Jul 4 '16 at 23:27
• @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$. – André Nicolas Jul 4 '16 at 23:33
• Yes, now why is the following true, "Thus $f(x)\equiv 0(mod$ $p)$" has at least n+1 distinct solutions modulo p? – TheMathNoob Jul 4 '16 at 23:34
• @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. – André Nicolas Jul 4 '16 at 23:39
• how do we conclude $a_0 \equiv 0(mod$ $p)$ if it's stated in the theorem that it's not. – TheMathNoob Jul 4 '16 at 23:42