USAMO 2006 — Days 1 and 2 Question 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$.

Proposed by Kiran Kedlaya (credited in the supplied source).