Problem

Source: ELMO SL 2018 N4

Tags: number theory



Say a positive integer $n>1$ is $d$-coverable if for each non-empty subset $S\subseteq \{0, 1, \ldots, n-1\}$, there exists a polynomial $P$ with integer coefficients and degree at most $d$ such that $S$ is exactly the set of residues modulo $n$ that $P$ attains as it ranges over the integers. For each $n$, find the smallest $d$ such that $n$ is $d$-coverable, or prove no such $d$ exists. Proposed by Carl Schildkraut