2

Let $p$ be an odd prime and $a_1, a_2,...,a_p$ be integers. Prove that the following two conditions are equivalent:

$1)$ ：There exists a polynomial $P(x)$ with degree $\leq \frac{p-1}{2}$ such that $P(i) \equiv a_i \pmod p$ for all $1 \leq i \leq p$

$2)：$ foy any integer $k(0\le k\le \dfrac{p-3}{2})$,we have $$\sum_{i=1}^{p}a_{i}i^k\equiv 0\pmod p$$

This problem is from when I deal 2015CMO3 problem at last step.seelinks

I think use this well konwn $$\sum_{i=1}^{p}i^m\equiv 0\pmod p,0\le m<p-1,m\in Z$$ and $$\sum_{i=1}^{p}i^m\equiv 1+1+\cdots+1=-1\pmod p,m=p-1,m\in Z$$

also see: Polynomial interpolating sequence mod p has small degree

But I can't it.Thanks

math110
  • 93,304

1 Answers1

1

Part 1. $(1)\implies (2)$.

Write $$P(x)=\sum_{i=0}^{\frac{p-1}2}c_ix^i,$$ where $c_i$ may be $0$. Then, for any $0\leq k\leq \frac{p-3}2$, $$\sum_{x=1}^pa_xx^k=\sum_{x=1}^px^kP(x)=\sum_{x=1}^px^k\sum_{i=0}^{\frac{p-1}2}c_ix^i=\sum_{i=0}^{\frac{p-1}2}c_i\sum_{x=1}^px^{k+i};$$ since each $k+i$ is at most $\frac{p-1}2+\frac{p-3}2=p-2$, the inner sums are all $0$, so this sum is $0$.

Part 2. $(2)\implies (1)$.

Consider the polynomial $$P(x)=\sum_{y=1}^pa_y\big(1-(x-y)^{p-1}\big).$$ At any $x\in\{1,2,\dots,p\}$, all the terms with $y\neq x$ give $0$ modulo $p$ (using Fermat's little theorem), while the term with $y=x$ gives $a_x$, so $P(x)\equiv a_x\pmod p$. We need only show that $\deg P\leq \frac{p-1}2$. Indeed, write \begin{align*} P(x) &=\sum_{y=1}^p a_y-\sum_{y=1}^p a_y(x-y)^{p-1}\\ &=-\sum_{y=1}^pa_y\sum_{j=0}^{p-1}\binom{p-1}jx^j(-y)^{p-1-j}\\ &=\sum_{j=0}^{p-1}x^j\binom{p-1}j(-1)^{p-j}\sum_{y=1}^pa_yy^{p-1-j}. \end{align*} For $j>\frac{p-1}2$, the inner sum is $\sum_{y=1}^p a_yy^k$ for $k\leq \frac{p-3}2$, and is thus $0$. So, the coefficient of $x^j$ in $P(x)$ for $j>\frac{p-1}2$ is $0$, and thus $\deg P\leq \frac{p-1}2$ as desired.

Carl Schildkraut
  • 32,931