I have the following question from USAMO 2006:
"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$."
How do I prove that for a prime $p$, if $s$ is a divisor of $p-1$, then we can not find the required integers?
Best Answer
The solution says that from the assumption $sk=p-1$ and the given conditions, the first column (in red) is as follows (basically, we need to pay attention only to the first column) :
\begin{array}{ccccc} \mbox{Row 1}& \color{red}{s\equiv ((1-1)k+1)s}& 2s&\cdots& ks\\ \mbox{Row 2}& \color{red}{s-1\equiv ((2-1)k+1)s}& 2s-1& \cdots&ks-1\\ \vdots&\color{red}{\vdots}&\vdots&\ddots&\vdots\\ \mbox{Row $n_r$}&\color{red}{sn\equiv ((n_r-1)k+1)s}\\ \vdots&\color{red}{\vdots}&\vdots&\ddots&\vdots\\ \mbox{Row $m_r$}&\color{red}{sm\equiv ((m_r-1)k+1)s}\\ \vdots&\color{red}{\vdots}&\vdots&\ddots&\vdots\\ \mbox{Row }s& \color{red}{1\equiv ((s-1)k+1)s}& s+1& \cdots& (k-1)s+1 \end{array}
Now, we have
$((m_r-1)k+1)s\equiv sm\pmod p\color{red}{\lt} sn\equiv ((n_r-1)k+1)s\pmod p$
$((m_r-1)k+1)s\color{red}{\gt} ((n_r-1)k+1)s$
(be careful, this is not $((m_r-1)k+1)s\pmod p\gt ((n_r-1)k+1)s\pmod p$)
so, it follows that there has to be at least one $0\pmod p$ between $sm\pmod p$ and $sn\pmod p$, which is impossible.