MathDB
Polynomial interpolating sequence mod p has small degree

Source: China Mathematical Olympiad 2016 Q3

December 16, 2015
algebrapolynomialmodular arithmeticnumber theory

Problem Statement

Let pp be an odd prime and a1,a2,...,apa_1, a_2,...,a_p be integers. Prove that the following two conditions are equivalent:
1) There exists a polynomial P(x)P(x) with degree ≤p−12\leq \frac{p-1}{2} such that P(i)≡ai(modp)P(i) \equiv a_i \pmod p for all 1≤i≤p1 \leq i \leq p
2) For any natural d≤p−12d \leq \frac{p-1}{2}, ∑i=1p(ai+d−ai)2≡0(modp) \sum_{i=1}^p (a_{i+d} - a_i )^2 \equiv 0 \pmod p where indices are taken (modp)\pmod p
Back to ProblemsView on AoPS