2006 USAMO Problems/Problem 1
(Kiran Kedlaya) 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 .
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.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
- <url>viewtopic.php?t=84548 Discussion on AoPS/MathLinks</url>
|2006 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|