Problem:
Let p be a prime, and let a1​,a2​,…,ap​ be integers. Show that there exists an integer k such that the numbers
a1​+k,a2​+2k,…,ap​+pk
produce at least 21​p distinct remainders upon division by p.
Solution:
The statement is trivial for p=2, so assume p=2q+1 is odd. Create a p×p table of numbers, as follows:
a1​+1⋅0a1​+1⋅1⋮a1​+1⋅(p−1)​a2​+2⋅0a2​+2⋅1⋮a2​+2⋅(p−1)​⋯⋯⋱⋯​ap​+p⋅0ap​+p⋅1⋮ap​+p⋅(p−1)​
Interpret all the numbers above modulo p. Examine two different columns, say columns i and j. We claim they agree (modulo p ) in exactly one row. Indeed, ai​+ik≡aj​+jk(modp) holds if and only if (i−j)k≡aj​−ai​(modp). Since p is prime and iî€ â‰¡j(modp), this condition holds for a unique value of k( namely, k≡(aj​−ai​)(i−j)−1(modp)).
Thus, there are (2p​)=2p(p−1)​=pq pairs of integers that are congruent modulo p and lie in the same row of the table. Since there are only p rows, some row, say {an​+nk}n​, must contain at most q such pairs.
We claim that this k satisfies our requirement. Indeed, if we read the p entries in this row one by one, each entry either is distinct from all the previous ones, or is congruent to at least one previous entry and thereby completes a pair. Since the latter case happens at most q times, there must be at least p−q=(p+1)/2 distinct entries (modulo p ), completing the proof.
The problems on this page are the property of the MAA's American Mathematics Competitions