Let $p$ be a prime and $P\in \mathbb{R}[x]$ be a polynomial of degree less than $p-1$ such that $\lvert P(1)\rvert=\lvert P(2)\rvert=\ldots=\lvert P(p)\rvert$. Prove that $P$ is constant.
Problem
Source: 2023 Serbia TST Problem 4
Tags: algebra, polynomial, Serbia, TST
gvole
22.05.2023 16:43
Here's my solution from contest. I think this is the cleanest way to do it.
Apply a linear transform so that the two values of $P$ are 0 and 1, then take the $p-1$-th finite difference to obtain:\[\sum(-1)^i\binom{p-1}{i}=0\]over all the $i$ where $P(i)=1$. You can check (and it's well known) that this holds only when $P$ is always 1 or always 0 in our set, which completes the proof since the degree is less than $p$.
cefer
23.05.2023 05:31
If $p=2$, then $P$ has degree less than $1$, which means $P$ is constant. Without loss of generality, let $p >2$ and assume $$\lvert P(1)\rvert=\lvert P(2)\rvert=\ldots=\lvert P(p)\rvert = 1$$By Lagrange Interpolation Theorem we have $$\sum_{i= 0}^{p - 1} (-1)^i\binom{p-1}{i}P(i + 1) = 0$$Since $$\binom{p-1}{i} = \frac{(p-1)!}{i! (p-1-i)!} \equiv (-1)^i \frac{(p-1)!}{(p-1)(p-2)\cdots (p-i)(p-1-i)!} \equiv (-1)^i \pmod{p}$$we get $$0 = \sum_{i= 0}^{p - 1} (-1)^i\binom{p-1}{i}P(i + 1) \equiv \sum_{i= 0}^{p - 1} P(i+ 1) \pmod{p}$$Using $P(i + 1) = \pm 1$, we get $$-p \leq \sum_{i= 0}^{p - 1} P(i+ 1) \leq p \qquad \Longrightarrow \qquad \sum_{i= 0}^{p - 1} P(i+ 1) \in \{-p, 0, p\}$$Since $p$ is odd, the above sum can not be equal to $0$. So, the sum should be either $p$ or $-p$, and this can be if and only if all given values of $P$ are $1$ or all are $-1$. This means $P$ gets the same value at $p$ distinct points and therefore it must be a constant polynomial.
mathscrazy
23.05.2023 08:13
If $p=2$, deg$P <1$, so constant, done. Let $p >2$. If $P(1)=\dots = P(p)=0$, $P$ has atleast $p$ roots, which is more than its degree. So $P \equiv 0$, done. Hence, WLOG scale $P$ to $\lvert P(1)\rvert=\lvert P(2)\rvert=\ldots=\lvert P(p)\rvert = 1$ and $P(p)=1$.
From values of $P(1),P(2),\dots,P(p-1)$, by lagrange interpolation, we get $P(x) = \sum_{i=1}^{p-1} P(i) \prod_{1 \leqslant i \neq j \leqslant p-1} \frac{x-j}{i-j}$. Hence,
$$P(p)= \sum_{i=1}^{p-1} P(i) \prod_{1 \leqslant i \neq j \leqslant p-1} \frac{p-j}{i-j} = \sum_{i=1}^{p-1} P(i) \frac{\frac{(p-1)!}{(p-i)}}{(i-1)!(p-i-1)!(-1)^i} = \sum_{i=1}^{p-1} P(i) (-1)^i {p-1 \choose i-1}$$Using the result that ${p-1 \choose k} \equiv (-1)^k \text{ mod }p$, going mod $p$ in last equation : $$1=P(p) \equiv \sum_{i=1}^{p-1} P(i) (-1)^i \cdot (-1)^{i-1} \equiv - \sum_{i=1}^{p-1} P(i)
\text{ (mod } p)$$Also, $P(i) = \pm 1$, and $p-1$ is even, hence : $\sum_{i=1}^{p-1} P(i)$ is even and $- (p-1) \leqslant \sum_{i=1}^{p-1} P(i) \leqslant p-1$. But by last equation, it is $-1$ mod $p$.
Hence, $\sum_{i=1}^{p-1} P(i) = p-1$, which can happen only when all $P(i)$ are $1$. Hence $P$ takes value one, $p$ times, which is more than its degree. Hence $P\equiv 1$. Hence, constant, done.