USAMO 2006 Problem 1

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.