# Difference between revisions of "2018 USAJMO Problems/Problem 5"

(→Solution) |
(→Solution) |
||

Line 4: | Line 4: | ||

==Solution== | ==Solution== | ||

− | |||

<math>\textbf{Lemma: }</math> For fixed <math>i\neq j,</math> where <math>i, j\in\{1, 2, ..., p\},</math> the statement <math>a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}</math> holds for exactly one <math>k\in {1, 2, ..., p}.</math> | <math>\textbf{Lemma: }</math> For fixed <math>i\neq j,</math> where <math>i, j\in\{1, 2, ..., p\},</math> the statement <math>a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}</math> holds for exactly one <math>k\in {1, 2, ..., p}.</math> |

## Revision as of 09:53, 21 April 2018

## Problem 5

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 .

## Solution

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.

(sujaykazi)