2018 USAJMO Problems/Problem 5

Problem 5

Let $p$ be a prime, and let $a_1, \dots, a_p$ be integers. Show that there exists an integer $k$ such that the numbers $a_1 + k, a_2 + 2k, \dots, a_p + pk$ produce at least $\tfrac{1}{2} p$ distinct remainders upon division by $p$ .

Solution

Notice that, if $a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}$ for some $k\in {1, 2, ..., p},$ then $a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}$ is false for all other $k'\in {1, 2, ..., p}.$

Page

Toolbox

Search

2018 USAJMO Problems/Problem 5

Problem 5

Solution