Difference between revisions of "2006 USAMO Problems/Problem 1"
5849206328x (talk | contribs) m (→Solution) |
Mathgeek2006 (talk | contribs) m (→Solution 1) |
||
Line 16: | Line 16: | ||
Now consider the following array modulo p: | Now consider the following array modulo p: | ||
− | < | + | <cmath>\begin{array}{ccccc} |
− | \mbox{ | + | \mbox{Row 1}& s& 2s&\hdots& ks\\ |
− | \vdots\\ | + | \mbox{Row 2}& s-1& 2s-1& \hdots&ks-1\\ |
− | \mbox{ | + | \vdots&\vdots&\vdots&\ddots&\vdots\\ |
+ | \mbox{Row }s& 1& s+1& \hdots& (k-1)s+1 | ||
+ | \end{array}</cmath> | ||
Obviously, there are <math>s</math> rows and <math>k</math> columns. The first entry of each row is simply <math>((r-1)k+1)s\mod p</math>. Since we wish for <math>sm\mod p</math> and <math>sn\mod p</math> to both be in the first column, while also satisfying the given conditions, we can easily see that <math>sm</math> must be in a row <math>m_r</math> with <math>m_r>n_r</math>, where <math>n_r</math> denotes the row <math>sn \mod p</math> is in. However, since the values of each entry decreases while <math>((r-1)k+1)s</math> keeps increasing, we can see that the condition can never be satisfied and thus, <math>s\not|(p-1).</math> | Obviously, there are <math>s</math> rows and <math>k</math> columns. The first entry of each row is simply <math>((r-1)k+1)s\mod p</math>. Since we wish for <math>sm\mod p</math> and <math>sn\mod p</math> to both be in the first column, while also satisfying the given conditions, we can easily see that <math>sm</math> must be in a row <math>m_r</math> with <math>m_r>n_r</math>, where <math>n_r</math> denotes the row <math>sn \mod p</math> is in. However, since the values of each entry decreases while <math>((r-1)k+1)s</math> keeps increasing, we can see that the condition can never be satisfied and thus, <math>s\not|(p-1).</math> |
Latest revision as of 21:13, 25 April 2015
Contents
Problem
(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 .
Solutions
Solution 1
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.
See also
- <url>viewtopic.php?t=84548 Discussion on AoPS/MathLinks</url>
2006 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.