2001 IMO Shortlist Problems/N4
Problem
Let be a prime number. Prove that there exists an integer with such that neither nor is divisible by .
Solution (Elementary Group Theory)
Let us work in the group .
Note that the order of this group is . Since is cyclic, we know that it is isomorphic to .
We can then conclude how many residues there are such that . For some arbitrary natural number , one has: Therefore there are only possible values of . It's also notable that if this is true for , then it is also true for and . This implies that there are also different values of a such that . It also implies that if and only if has this property, so does , and when working in . The squares also have their inverses which are guaranteed to have the property.
There exists no numbers such that as and . Therefore, at most half of the values where are in range . We can again remove some of the potential values by squaring all and taking their inverse. As long as no more than half of the values in that range can have the required property, there must be a pair and that satisfy the requirements by the pigeonhole principle.
Lastly, you must show that there is a pair for . This is satisfied by .