First suppose that $s$ is a divisor of $p-1$; write $d = (p-1)/s$. As $x$ varies among $1, 2, \dots, p-1$, $\{sx/p\}$ takes the values $1/p, 2/p, \dots, (p-1)/p$ once each in some order. The possible values with $\{sx/p\} < s/p$ are precisely $1/p, \dots, (s-1)/p$. From the fact that $\{sd/p\} = (p-1)/p$, we realize that the values $\{sx/p\} = (p-1)/p, (p-2)/p, \dots, (p-s+1)/p$ occur for
$$x = d, 2d, \dots, (s-1)d$$
(which are all between 0 and $p$), and so the values $\{sx/p\} = 1/p, 2/p, \dots, (s-1)/p$ occur for
$$x = p - d, p - 2d, \dots, p - (s-1)d,$$
respectively. From this it is clear that $m$ and $n$ cannot exist as requested.

Conversely, suppose that $s$ is not a divisor of $p-1$. Put $m = \lfloor p/s \rfloor$; then $m$ is the smallest positive integer such that $\{ms/p\} < s/p$, and in fact $\{ms/p\} = (ms - p)/p$. However, we cannot have $\{ms/p\} = (s-1)/p$ or else $(m-1)s = p-1$, contradicting our hypothesis that $s$ does not divide $p-1$. Hence the unique $n \in \{1, \dots, p-1\}$ for which $\{nx/p\} = (s-1)/p$ has the desired properties (since the fact that $\{nx/p\} < s/p$ forces $n \ge m$, but $m \ne n$).

We prove the contrapositive statement:
Let $p$ be a prime number and let $s$ be an integer with $0 < s < p$. Prove that the following statements are equivalent:
(a) $s$ is a divisor of $p-1$;
(b) if integers $m$ and $n$ are such that $0 < m < p$, $0 < n < p$, and
$$\{\frac{sm}{p}\} < \{\frac{sn}{p}\} < \frac{s}{p},$$
then $0 < n < m < p$.
Since $p$ is prime and $0 < s < p$, $s$ is relatively prime to $p$ and
$$m_1s + a_1p = 1,\ m_2s + a_2p = 2, \dots, m_s s + a_s p = s.$$
Hence $\{m_k s/p\} = k/p$ for $1 \le k \le s$.
Statement (b) holds if and only $0 < m_s < m_{s-1} < \dots < m_1 < p$. For $1 \le k \le s-1$, $m_k s - m_{k+1} s = (a_{k+1} - a_k) p - 1$, or $(m_k - m_{k+1}) s \equiv -1 \pmod p$. Since $0 < m_{k+1} < m_k < p$, by (1), we have $m_k - m_{k+1} = d$. We conclude that (b) holds if and only if $m_s, m_{s-1}, \dots, m_1$ form an arithmetic progression with common difference $-d$. Clearly $m_s = 1$, so $m_1 = 1 + (s-1)d = jp - d + 1$ for some $j$. Then $j=1$ because $m_1$ and $d$ are both positive and less than $p$, so $sd = p-1$. This proves (a).

Conversely, if (a) holds, then $sd = p-1$ and $m_k \equiv -d s m_k \equiv -d k \pmod p$. Hence $m_k = p-dk$ for $1 \le k \le s$. Thus $m_s, m_{s-1}, \dots, m_1$ form an arithmetic progression with common difference $-d$. Hence (b) holds.