2018 USAMO Problems/Problem 4
Let be a prime, and let be integers. Show that there exists an integer such that the numbers produce at least distinct remainders upon division by .
For fixed where the statement holds for exactly one
Notice that the left side minus the right side is congruent to modulo For this difference to equal there is a unique solution for modulo given by where we have used the fact that every nonzero residue modulo has a unique multiplicative inverse. Therefore, there is exactly one that satisfies for any fixed
Suppose that you have graphs and graph consists of the vertices for all Within any graph vertices and are connected by an edge if and only if Notice that the number of disconnected components of any graph equals the number of distinct remainders when divided by given by the numbers
These graphs together have exactly one edge for every unordered pair of elements of so they have a total of exactly edges. Therefore, there exists at least one graph that has strictly fewer than edges, meaning that it has more than disconnected components. Therefore, the collection of numbers for this particular value of has at least distinct remainders modulo This completes the proof.