Difference between revisions of "2006 USAMO Problems/Problem 1"
Mathcrazed (talk | contribs) |
|||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math> | + | 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 7: | Line 7: | ||
</center> | </center> | ||
− | if and only if <math> | + | if and only if <math>s </math> is not a divisor of <math>p-1 </math>. |
− | Note: For <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>. |
== Solution == | == Solution == | ||
− | {{ | + | 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 \mod p < sn \mod p< s\mod p</math>. |
+ | Now consider the following array modulo p: | ||
+ | |||
+ | <math>\mbox{row 1}\qquad s\qquad 2s\qquad \hdots\qquad ks\ | ||
+ | \mbox{row 2}\qquad s-1\qquad 2s-1\qquad \hdots\qquad ks-1\ | ||
+ | \vdots\ | ||
+ | \mbox{row s}\qquad 1\qquad s+1\qquad \hdots\qquad (k-1)s+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 \mbox{and} 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>. | ||
+ | |||
+ | Note that for <math>0<l<j</math>, <math>ls\ge s\mod p</math>. Thus, the first integer multiplied by s modulo p that will be less than s is <math>j+1.</math> <math>(j+1)s\equiv s-r-1\mod p</math>. Since <math>\lbrace s,2s,\hdots,js,(j+1)s,\hdots,xs,\hdots,(p-1)s \rbrace</math> is a complete residue system mod p with the exception of the 0 term, we can find an <math>x>j+1</math> such that <math>xs \equiv s-1 \mod p</math>. | ||
+ | |||
+ | Thus, choose <math>m=j+1</math> and <math>n=x</math> to complete the proof. | ||
== Resources == | == Resources == |
Revision as of 20:24, 13 April 2008
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 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.