Polynomial always congruent to $0$ or $1$ Problem: We are given a polynomial $P(x) \in \mathbb{Z}[x]$ and some prime $p$, such that $P(0)=0$,  $P(1) = 1$ and for every natural number $n$, $P(n)$ is congruent to $0$ or $1$ modulo $p$. Prove $P(x)$ is of degree at least $p-1$.
My observations:

*

*$a\equiv b \implies P(a) \equiv P(b)$ so we can only consider remainders of $P(0), P(1), \dots, P(p-1)$.

*$P(n)$ must be divisible by $n$.

*$P(n)^2 - P(n) \equiv 0$ for every $n$ so there must be a factor $x-n$ or some irreducible trinomial that is divisible by $p$ for $n$.

*we could assume $\deg P(x) < p - 1$ and then show it has the same values in $p$ points as some other polynomial, then show that polynomial does not satisfy $P(0)=0$ and $P(1) = 1$
However, I don't know how to finish the solution.
 A: We are working in $ \mathbb{Z}_p [x]$. Any rational number should be interpreted accordingly in $ \mathbb{Z}_p$.
Recall lagrange interpolation: If a polynomial satisfies $ P(i) = y_i$, then
$$P(x) = \left[\sum_i y_i \prod_{j\neq i } \frac{ x - j}{i - j}\right]    +A(x)\prod_i(x-i). $$
We are given that $ y_i = 0, 1$ and specific values $ y_0 = 0, y_1 = 1$.
Claim: The polynomial in the parenthesis has degree $ p-1$.
Proof: The products $\prod_{j\neq i } \frac{ x - j}{i - j}$ each have degree $p-1$ and an (identical) leading coefficient of $\frac{1}{(-1)^{p-1} (p-1)!} \equiv (-1)^{p}$.
Hence, the coefficient of $ x^{p-1} $ in $\sum_i y_i \prod_{j\neq i } \frac{ x - j}{i - j}$ is $ - \sum y_i$.
This value is between $- (p-1)$ and $-1$, so in particular it is not 0 (in $\mathbb{Z}_p$).
Hence, the polynomial in the parenthesis has degree exactly $p-1$.
Corollary: Since the other term in $P(x)$ has degree at least $p$ (or 0), hence the problem statement follows.

Notes

*

*When first approaching this problem, it's natural to consider the special case where $f(i) = 1$ and $f(j) = 0$ for $i\neq j$. We can determine that (EG through brute force or otherwise) this polynomial has degree $p-1$ and leading coefficient $p-1$. (This is in fact the lagrange basis polynomials $\prod_{j\neq i } \frac{ x - j}{i - j}$.)

*The necessary condition in the problem is $ \sum y_i \neq 0 \pmod{p}$. Any solution will likely have to make use of this.

*

*As an example, we can show that if $P(x)$  has degree $\leq p-2$, then $ p \mid P(0) + P(1) + P(2) + \ldots + P(p-1)$. Since this condition is not satisfied, thus the degree is at least $p-1$.



*Another approach could be to show that the coefficient of $x^{p-1}$ is $ - \sum y_i$.

*

*This follows from using the method of differences to calculate the coefficient of $x^{p-1}$ as



$$ \frac{1}{(p-1)!} \left[ {p-1 \choose 0} y_1 - {p-1 \choose 1} y_2 + {p-1 \choose 2 } y_3 + \ldots + (-1)^{p+1}{p-1 \choose 0 } y_p \right]. $$

*

*It's not immediately clear to me that OP's observation of $[P(x)]^2 - P(x) \equiv 0$ can lead to a solution. The condition that $y_i \in \{0, 1 \}$ isn't necessary, and we just need $y_i \in \{a, b\}$.

