MathDB

6

Part of 2019 IOM

Problems(1)

Remainders of a polynomoal mod p

Source: International Olympiad of Metropolises Problem 6

9/4/2019
Let pp be a prime and let f(x)f(x) be a polynomial of degree dd with integer coefficients. Assume that the numbers f(1),f(2),…,f(p)f(1),f(2),\dots,f(p) leave exactly kk distinct remainders when divided by pp, and 1<k<p1<k<p. Prove that p−1d≤k−1≤(p−1)(1−1d). \frac{p-1}{d}\leq k-1\leq (p-1)\left(1-\frac1d \right) .
Dániel Domán, Gauls Károlyi, and Emil Kiss
algebrapolynomial