Difference between revisions of "2006 USAMO Problems/Problem 1"

m (Solution 1)
(5 intermediate revisions by 3 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>.
  
== Solution ==
+
== Solutions ==
  
 +
=== 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 \mod p < sn \mod p< s\mod p</math>.
 
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:
 
Now consider the following array modulo p:
  
<math>\mbox{row 1}\qquad s\qquad 2s\qquad \hdots\qquad ks\\
+
<cmath>\begin{array}{ccccc}
\mbox{row 2}\qquad s-1\qquad 2s-1\qquad \hdots\qquad ks-1\\
+
\mbox{Row 1}& s& 2s&\hdots& ks\\
\vdots\\
+
\mbox{Row 2}& s-1& 2s-1& \hdots&ks-1\\
\mbox{row s}\qquad 1\qquad s+1\qquad \hdots\qquad (k-1)s+1</math>
+
\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 \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>.
 
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 33:
 
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.
  
== Resources ==
+
{{alternate solutions}}
 +
 
 +
== See also ==
 +
* <url>viewtopic.php?t=84548 Discussion on AoPS/MathLinks</url>
  
* [[2006 USAMO Problems]]
+
{{USAMO newbox|year=2006|before=First Question|num-a=2}}
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=490569#p490569 Discussion on AoPS/MathLinks]
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 21:13, 25 April 2015

Problem

(Kiran Kedlaya) Let $p$ be a prime number and let $s$ be an integer with $0 < s < p$. Prove that there exist integers $m$ and $n$ with $0 < m < n < p$ and

$\left\{ \frac{sm}{p} \right\} < \left\{ \frac{sn}{p} \right\} < \frac{s}{p}$

if and only if $s$ is not a divisor of $p-1$.

Note: For $x$ a real number, let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x$, and let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of $x$.

Solutions

Solution 1

We proceed by contradiction. Assume that $s|(p-1)$. Then for some positive integer $k$, $sk=p-1$. The conditions given are equivalent to stating that $sm \mod p < sn \mod p< s\mod p$. Now consider the following array modulo p:

\[\begin{array}{ccccc} \mbox{Row 1}& s& 2s&\hdots& ks\\ \mbox{Row 2}& s-1& 2s-1& \hdots&ks-1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \mbox{Row }s& 1& s+1& \hdots& (k-1)s+1 \end{array}\]

Obviously, there are $s$ rows and $k$ columns. The first entry of each row is simply $((r-1)k+1)s\mod p$. Since we wish for $sm\mod p$ and $sn\mod p$ to both be in the first column, while also satisfying the given conditions, we can easily see that $sm$ must be in a row $m_r$ with $m_r>n_r$, where $n_r$ denotes the row $sn \mod p$ is in. However, since the values of each entry decreases while $((r-1)k+1)s$ keeps increasing, we can see that the condition can never be satisfied and thus, $s\not|(p-1).$


To prove the other direction, let $sj+r=p-1$ for positive integers $j$ and $r$ with $j$ being the largest integer such that $sj<p-1$ and $r<s$. Since $s\not|(p-1)$, $1<s<p-1$.

Note that for $0<l<j$, $ls\ge s\mod p$. Thus, the first integer multiplied by s modulo p that will be less than s is $j+1.$ $(j+1)s\equiv s-r-1\mod p$. Since $\lbrace s,2s,\hdots,js,(j+1)s,\hdots,xs,\hdots,(p-1)s \rbrace$ is a complete residue system mod p with the exception of the 0 term, we can find an $x>j+1$ such that $xs \equiv s-1 \mod p$.

Thus, choose $m=j+1$ and $n=x$ 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 (ProblemsResources)
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. AMC logo.png