Anyway, so the answer is $n=2$ because $Q(x)=P(x)-1$ is not identically $0$ (since $n>0$) and has at least two distinct real roots, which means that $deg(P) = deg(Q) \geq 2$. Conversely, $P(x) = 2003x(x-1) + 1$ is a suitable polynomial. I hope I did not too wrong this time. Pierre.

Of course, this is the obvious answer. Still, I wonder why in the statement of the problem the remainders are $0$ or $1$. Maybe there's some stronger result and our new member did not quote the problem correctly.

Then I think it's from the 1997 shortlist. We could do this: Reduce the coefficients modulo $p$, and regard the polynomial as being over $\mathbb Z_p$. Now, assuming it has degree $\le p-1$, because this is the interesting case, attempt to construct it using Lagrange's interpolation formula. The resulting polynomial will have the leading coefficient equal to $-k$, where $k$ is the number of residues among $0,1,\ldots,p-1$ for which it takes the value $1$. Since $0<k<p,\ k$ cannot be zero modulo $p$, so the polynomial has a non-vanishing coefficient corresponding to its $p-1$'th degree monomial.

Alternatively, we may use that \[1^k+2^k+\ldots +(p-1)^k \equiv 0 \quad (\mod {p})\] for all $k<p-1$. Assuming that $\deg P <p-1$ this yields \[f(0)+f(1)+\ldots +f(p-1) \equiv 0 \quad (\mod p).\] Since $f(0)=0,f(1)=1$ and $f(k)\equiv 0 \; \mbox{or} \; 1 (\mod p)$, this is a contradiction.

from which theorem or lemma you got this this yelds $f(0)+f(1)....f(p-1)=0(mod p)$

Let's call $A$ the set of values $m\in\{0,1,2,\dots ,p-1\}$ such that $f(m) \equiv 1\mod p$ and define $p(n)=f(n)+\sum_{i\in A} ((x-i)^{p-1}-1) $ Clearly $p(n)\equiv 0\mod p\hspace{0.1cm} \forall n\in \mathbb{Z}$, so for a know fact $p(n)\equiv 0 \vee \deg(p(n))\geq p$ In both cases $\deg(f(n)) \geq p-1$ Q.E.D.

Just assume the contrary i.e. $deg f$ $\ge p-2$ and then from above information construct $P(x) $ using $Lagrange$ $Interpolation$... And at last you will get all $f(i)$ to be $0$ $mod p$ .. A Contradiction to $f(1) $ = $1$..

The key Corollary: If $f$ is a polynomial with integer coefficients and $\deg(f)<p-1$ then $p|\sum_{i=0}^{p-1} f(i)$ In this problem,$\sum_{i=0}^{p-1} f(i) <p \pmod p$,so by the Corollary,$\deg(f)>p-1$

The key Lemma is the following: Lemma. If $f$ is a polynomial with integer coefficients and $\deg f < p-1$, then $$f(0)+f(1)+\cdots+f(p-1) \equiv 0 \pmod p.$$ Proof. We can reduce to the monomial case, which is well-known. $\blacksquare$ But now for this function $f$, each $f(i)$ with $0 \leq i \leq p-1$ is congruent to $0$ or $1$, so the LHS is congruent to at most $p-1$ modulo $p$, making it impossible to get a multiple of $p$.

Note that $f$ is clearly not a constant polynomial, so $d\geq 1$. Hence, $p=2$ is trivial. Hence, take $p>2$. Assume for contradiction that $d\leq p-2$. Note that from Lagrange Interpolation Formula, we have that \[f(x)=\sum_{j=0}^{p-1}f(j)\prod_{i\ne j}\frac{x-i}{j-i}\]Note that $f$ is the unique polynomial obtained by Lagrange Interpolation, as $d\leq p-2$. Morevoer, since $d\leq p-2$, the coefficient of $p-1$ in $f$ is zero (leading coefficient). So, we have \[0=\sum_{j=0}^{p-1}f(j)\prod_{i\ne j}\frac1{j-i}=\sum_{j=0}^{p-1}\frac{f(j)(-1)^{p-1-j}}{j!(p-j-1)!}\]Since $p-1$ is even, we have \[\sum_{j=0}^{p-1}(-1)^j\binom{p-1}{j}f(j)=0\]However, we know that $\binom{p-1}{j}\equiv\frac{(p-1)\cdot(p-2)\cdots(p-j)}{1\cdot2\cdots j}\equiv(-1)^{j}\pmod{p}$ Hence, we have \[f(0)+f(1)+\cdots+f(p-1)\equiv 0 \pmod{p}\]Since $f(n)\equiv0,1\pmod{p}$, it is forced that $f(0)\equiv f(1)\equiv\cdots f(p-1) \equiv x \pmod{p}$ where $x\in\{0,1\}$. However, since $f(0)=0$ and $f(1)=1$, we have that $0\equiv1\pmod{p}$, which is impossible. Hence, $d\geq p-1$ is true. $\blacksquare$

An important claim is that \[\sum_{i=1}^{p-1} f(i) \equiv 0\pmod{p}\]if $deg(f) < p-1$ which follows from the fact that $1^k + 2^k + \dots + (p-1)^k \equiv 0\pmod p$ for $\gcd(k, p-1) \neq p-1$. From this we get that $f$ must be constant modulo $p$ which is a contradiction by $f(0) \neq f(1)$, so $deg(f) \geq p-1$.

Finite differences solution!

Attachments: