Difference between revisions of "2006 USAMO Problems/Problem 1"
Mathcrazed (talk | contribs) |
(→Solution 1: bmod) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | + | (''Kiran Kedlaya'') Let <math>p</math> be a prime number and let <math>s</math> be an integer with <math>0 < s < p </math>. Prove that there exist integers <math>m</math> and <math>n</math> with <math>0 < m < n < p</math> and | |
− | Let <math>p</math> be a prime number and let <math>s</math> be an integer with <math>0 < s < p </math>. Prove that there exist integers <math>m</math> and <math>n</math> with <math>0 < m < n < p</math> and | ||
<center> | <center> | ||
Line 11: | Line 10: | ||
Note: For <math>x</math> a real number, let <math>\lfloor x \rfloor</math> denote the greatest integer less than or equal to <math>x</math>, and let <math>\{x\} = x - \lfloor x \rfloor</math> denote the fractional part of <math>x </math>. | Note: For <math>x</math> a real number, let <math>\lfloor x \rfloor</math> denote the greatest integer less than or equal to <math>x</math>, and let <math>\{x\} = x - \lfloor x \rfloor</math> denote the fractional part of <math>x </math>. | ||
− | == | + | == Solutions == |
− | We proceed by contradiction. Assume that <math>s|(p-1)</math>. Then for some positive integer <math>k</math>, <math>sk=p-1</math>. The conditions given are equivalent to stating that <math>sm \ | + | === Solution 1 === |
+ | We proceed by contradiction. Assume that <math>s|(p-1)</math>. Then for some positive integer <math>k</math>, <math>sk=p-1</math>. The conditions given are equivalent to stating that <math>sm \bmod p < sn \bmod p< s\bmod p</math>. | ||
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 | + | 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> |
To prove the other direction, let <math>sj+r=p-1</math> for positive integers <math>j</math> and <math>r</math> with <math>j</math> being the largest integer such that <math>sj<p-1</math> and <math>r<s</math>. Since <math>s\not|(p-1)</math>, <math>1<s<p-1</math>. | To prove the other direction, let <math>sj+r=p-1</math> for positive integers <math>j</math> and <math>r</math> with <math>j</math> being the largest integer such that <math>sj<p-1</math> and <math>r<s</math>. Since <math>s\not|(p-1)</math>, <math>1<s<p-1</math>. | ||
Line 29: | Line 31: | ||
Thus, choose <math>m=j+1</math> and <math>n=x</math> to complete the proof. | Thus, choose <math>m=j+1</math> and <math>n=x</math> to complete the proof. | ||
− | == | + | {{alternate solutions}} |
+ | |||
+ | == See also == | ||
+ | * <url>viewtopic.php?t=84548 Discussion on AoPS/MathLinks</url> | ||
− | + | {{USAMO newbox|year=2006|before=First Question|num-a=2}} | |
− | |||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 16:54, 22 June 2023
Contents
[hide]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.