MathDB

polynomial attains every possible value mod p

Source: 2019-20 International Dürer Competition,Category E+, P5

August 19, 2020

abstract algebraalgebrapolynomial

Problem Statement

Let

p

be prime and

k > 1

be a divisor of

p-1

. Show that if a polynomial of degree

k

with integer coefficients attains every possible value modulo

p

that is

(0,1,\dots, p-1)

at integer inputs then its leading coefficient must be divisible by

p

. Note: the leading coefficient of a polynomial of degree d is the coefficient of the

x_d

term.