2006 USAMO Problems/Problem 1
Problem
Let be a prime number and let
be an integer with
. Prove that there exist integers
and
with
and
if and only if is not a divisor of
.
Note: For a real number, let
denote the greatest integer less than or equal to
, and let
denote the fractional part of
.
Solution
We proceed by contradiction. Assume that . Then for some positive integer
,
. The conditions given are equivalent to stating that
.
Now consider the following array modulo p:
Obviously, there are rows and
columns. The first entry of each row is simply
. Since we wish for
and
to both be in the first column, while also satisfying the given conditions, we can easily see that
must be in a row
with
, where
denotes the row
is in. However, since the values of each entry decreases while
keeps increasing, we can see that the condition can never be satisfied and thus,
To prove the other direction, let for positive integers
and
with
being the largest integer such that
and
. Since
,
.
Note that for ,
. Thus, the first integer multiplied by s modulo p that will be less than s is
. Since
is a complete residue system mod p with the exception of the 0 term, we can find an
such that
.
Thus, choose and
to complete the proof.
Resources
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.