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

Revision as of 08:50, 5 August 2014

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:

$\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$

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.

@@ Line 10: / 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>.
-== 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>.
 Now consider the following array modulo p:
@@ Line 29: / Line 30: @@
 Thus, choose <math>m=j+1</math> and <math>n=x</math> to complete the proof.
+{{alternate solutions}}
 == See also ==

2006 USAMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

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

Revision as of 08:50, 5 August 2014

Contents

Problem

Solutions

Solution 1

See also