My solution (kinda hard to follow I think...)

BTW: The last line in the problem statement should say $\{ x \} = x - \lfloor x \rfloor,$ not $x = x - \lfloor x \rfloor$.

Another Solution (notice how I define a and b):

we have to show that when we list the numbers $1s, 2s, ..., (p-1)s$ reduced $\pmod p$, some two of the elements of $\{1, ..., s-1\}$ occur in increasing order from left to right IFF $s$ doesn't divide $p-1$. 1) assume $sk = p-1$ for some $k$. then $s(k+1) \equiv s-1 \pmod p$ $s(2k+1) \equiv s-2 \pmod p$ ... $s((s-1)k+1) \equiv 1\pmod p$ (and $(s-1)k+1 \leq p-1$) so when we list $1s, 2s, 3s, ..., (p-1)s$ reduced $\pmod p$, the numbers $\{1, ..., s-1\}$ occur in decreasing order. 2) assume $s$ doesn't divide $p-1$. let $a \in \{1, ..., p -1\}$ be the unique value in that set for which $as \equiv p - 1 \pmod p$. in particular, notice that $a \geq 2$ (because if $a = 1$, then $s = p-1$). then $s(a+1) \equiv s-1 \pmod p$, $s(2a+1) \equiv s-2 \pmod p$, ... $s((s-1)a+1) \equiv 1 \pmod p$ but since $s$ doesn't divide $p-1$, $as \geq p+p-1 = 2p-1$, so $(s-1)a+1 = sa-a+1 \geq 2p-1-(p-1)+1 = p + 1$. so let $j \in \{1, ..., s-1\}$ be the smallest value for which $ja + 1 > p - 1$ and let $b \in \{1, ..., p-1\}$ be the unique value in that set for which $ja + 1\equiv b \pmod p$. (notice that $j > 1$ because if $j = 1$ we'd have $a+1 = p$, in which case $s = 1 | p-1$.) then $b < a$ because of the way we defined $j$. then setting $m = b, n = a+1$ completes the proof.

if s does not divides p-1

if s divides p-1, then my solution is the same as the official solution

I was wondering if this worked for the if direction

I've been having much more trouble with this problem than any other USAMO #1, so I will probably have a mistake in the above solution. Furthermore, I realize that I am not a good solution writer, so I would appreciate any suggestions as to how to improve my solution. Thank you!

For any integer $a$, let $[a]$ denote the value of $a$ reduced modulo $p$, and let $s^{-1}$ be the inverse of $s$ modulo $p$. Observe that $\left \{ \frac{k}{p} \right \} = \frac{[k]}{p}$ for all integers $k$, so it is sufficient to show that there exist integers $m,n$ with $0<m<n<p$ and $[sm] < [sn] < s$ if and only if $s \not| p-1$. Let $b_i = [i s^{-1}]$ for integers $1 \leq i \leq s-1$. Observe that for any integer $k$ with $0 < [ks] < s$, ${b_{[ks}} \equiv (ks) s^{-1} \equiv k \pmod{p}$. Hence, if $0 < [ms] < [ns] < s$, then $m < n$ if and only if $b_m < b_n$. Hence, there do not exist integers $m,n$ with $0<m<n<p$ and $[sm] < [sn] < p$ if and only if $b_{s-1} < b_{s-2} < \ldots < b_1$. We claim that $\min(b_1, b_2, \ldots, b_{s-1}) = \lfloor \frac{p}{s} \rfloor + 1$. For $0 \leq k \leq s-1$, let $a_k = \lfloor \frac{kp}{s} \rfloor + 1$. Let $U$ be the set of all integers $u$ less than $p$ with $0 < [us] < s-1$. since $0 < a_1 < a_2 < \ldots < a_{s-1} < p$, and that $kp < s a_k < kp + s$ for $1 \leq k \leq s-1$, $U = \{a_1, a_2, \ldots, a_{s-1}\}$. On the other hand, it is clear that $U = \{b_1, b_2, \ldots, b_{s-1}\}$ as well, so $\{a_1, a_2, \ldots, a_{s-1}\} = \{b_1, b_2, \ldots, b_{s-1}\}$; in particular the smallest element of $\{b_1, b_2, \ldots, b_{s-1}\}$ must equal the smallest element of $\{a_1, a_2, \ldots, a_{s-1}\}$, which is $\lfloor \frac{p}{s} \rfloor + 1$, so our claim is proven. If $s | p - 1$, then we claim that $b_i = (s - i) (\frac{p-1}{s}) + 1$. Since $0 < (s-i)(\frac{p-1}{s}) + 1 < p$, and \[ s((s-1)(\frac{p-1}{s}) + 1) = (s-1)(p-1) + s \equiv 1-s+s \equiv 1 \pmod{p}, \] we indeed have $b_i = (s - i) (\frac{p-1}{s}) + 1$, whence $b_{s-1} < b_{s-2} < \ldots < b_1$, so the only if direction of the problem is proven. If $s \not | p - 1$, we claim that $b_{s-1} \neq \min(b_1, b_2, \ldots, b_{s-1}) = \lfloor \frac{p}{s} \rfloor + 1$, whence we could not have $b_{s-1} < b_{s-2} < \ldots < b_1$. If $b_{s-1} = \lfloor \frac{p}{s} \rfloor + 1$, then \[ s-1 \equiv s b_{s-1} = s + s \lfloor \frac{p}{s} \rfloor \pmod{p}, \] so \[ p-1 \equiv s \lfloor \frac{p}{s} \rfloor \pmod{p}. \] Since $p-1$ and $s \lfloor \frac{p}{s} \rfloor$ are both less than $p$, we must have \[ \frac{p-1}{s} = \lfloor \frac{p}{s} \rfloor = \frac{p}{s} - \left \{ \frac{p}{s} \right \}, \] whence $s | p - 1$, which is a contradiction.

Apologies for the revive - Could I get some feedback on this solution? Does it have any aspects that could be improved upon? I feel like it is simpler than the official solution I have.

I dun think you can multiply by p on the first two terms

va2010 wrote: I dun think you can multiply by p on the first two terms Why not? $p \times \left\{\frac{sm}{p}\right\}$ is indeed equal to $ms\pmod{p}.$

It's equivalent to $ms \bmod p < ns \bmod p < s$, where $x \bmod p$ means the remainder when $x$ is divided by $p$, by slight abuse of notation. We will assume $s \ge 2$ for simplicity, since the case $s = 1$ is clear. For any $x \in \{1, 2, \dots, s-1\}$ we define $f(x)$ to be the unique number in $\{1, \dots, p-1\}$ such that $s \cdot f(x) \bmod p = x$. Then, $m$ and $n$ fail to exist exactly when \[ f(s-1) < f(s-2) < \dots < f(1). \] We give the following explicit description of $f$: choose $t \equiv -s^{-1} \pmod p$, $0 < t < p$. Then $f(x) = 1 + (s-x) \cdot t \bmod p$. So our displayed inequality is equivalent to \[ (1+t) \bmod p < (1+2t) \bmod p < (1+3t) \bmod p < \dots < (1+(s-1)t) \bmod p. \]This just means that the sequence $1+kt$ never ``wraps around'' modulo $p$ as we take $k=1,2,\dots,s-1$. Since we assumed $s \ne 1$, we have $0 < 1+t < p$. Now since $1+kt$ never wraps around as $k=1,2,\dots,s-1$, and increases in increments of $t$, it follows that $1+kt < p$ for all $k = 1, 2, \dots, s-1$. Finally, as $1+st \equiv 0 \pmod p$ we get $1+st=p$. In summary, $m$, $n$ fail to exist precisely when $1 + st = p$. That is of course equivalent to $s \mid p-1$.

@v_Enhance could you elaborate on the final part of your proof? ("$1+t<p$ means $1+(s-1)t<p$. But $1+st\equiv0\pmod{p}$, so $1+st=p$.) Thanks!

Let $a'$ be the remainder when $a$ is divided by $p$. First observe that the initial condition is equivalent to $(sm)'<(sn)'<s$. We will first prove the if statement. Let $m$ be the smallest positive integer such that $(ms)'<s.$ This is equivalent to $p\le ms\le p+s-1$. Clearly there is only one value of $m$ that satisfies these conditions. However, $ms\neq p+s-1$ since $s$ does not divide $p-1$. Also, $ms\neq 0$ since $s\neq 1$. Therefore, $(ms)'<s-1$. Also, since $s$ does not divide $p$, there is an integer $0<n<p$ such that $(ns)'=s-1$. Therefore, we have found integers $m$ and $n$ that satisfy the conditions. We will prove the only if statement by showing that if $s$ is a divisor of $p-1$ then it is impossible to find such integers $m$ and $n$. Let $sk=p-1$. Then $(s(k+1))'=s-1<(s(2k+1))'=s-2<\cdots <(s((s-1)k+1)'$ and $k+1<2k+1<\cdots <(s-1)k+1$. Since there is a unique $0<i<p$ such that $(si)'=j$ for $0<j<p$, then the result follows. $\Box$

This was a pretty silly problem. Also, why do they have to make Day 1 all number theory? Anyway, here is my solution (probably not significantly distinct) Case 1 Let $s \mid p-1$ In this case, let $k=\frac{p-1}{s}$ Evidently, we see that the set of residues $\{1s,2s,...,(p-1)s\}=_{\bmod p} \{s,2s,...,sk(=p-1),s-1,2s-1,...,sk-1(=p-2),s-2,...\}$ and thus, our condition cannot hold. Case 2 Let $s$ not divide $p-1$ In this case, we show that our desired $m,n$ indeed exist. If $r(x,p)=r$ such that $x \equiv r \bmod p$ and $r \in \{0,1,2,...,p-1\}$. Clearly, we want $r(sm,p) < r(sn,p)<s$ and for this, let $k$ be the integer such that $sk<p<s(k+1)$. Now, since $s$ is not a divisor of $p-1$ we see that $sk<p-1<p<s(k+1)$ Choose $m=k+1$ and we notice that $1 \le r(sm,p) \le s-2$ and so we miss the residue $s-1$. Let $n$ be the number in $\{1,2,...,p-1\}$ such that $sn \equiv s-1 \bmod p$ then clearly, $0<m<n<p$ which satisfy our condition. This solves the problem.

Here is my solution. Let \(p=sq+r\) where \(q,r\) denote the quotient when \(p\) is divided by \(s\). Note \(s\mid p-1\iff r=1\), and that \(r>0\). We can find that the \(k\) such that \(0<\left\{\dfrac{sk}{p}\right\}<\dfrac{s}{p}\) satisfy \(k=\left\lceil\dfrac{tp}{s}\right\rceil\) for \(1\le t \le s-1\). When \(r=1\), note that \(k=\left\lceil\dfrac{tp}{s}\right\rceil=\left\lceil\dfrac{t(sq+1)}{s}\right\rceil=tq+\left\lceil\dfrac{t}{s}\right\rceil=tq+1\), so the sequence of valid \(k\) yield \(\left\{\dfrac{sk}{p}\right\}=\left\{\dfrac{stq+s}{p}\right\}=\dfrac{s-t}{sq+1}\). Finally, if we pick \(t_m, t_n\) corresponding to values of \(m, n\), we get \(m<n\iff t_m < t_n\iff \dfrac{s-t_m}{sq+1}>\dfrac{s-t_n}{sq+1}\), so no \(m,n\) exist. Now, when \(r > 1\), note that when \(t=1\), \(k=\left\lceil\dfrac{p}{s}\right\rceil=q+1\), so \(\left\{\dfrac{sk}{p}\right\}=\left\{\dfrac{s(q+1)}{p}\right\}=\dfrac{s-r}{p}<\dfrac{s-1}{p}\). Thus, we can select \(m=q+1\) and \(n\) such that \(\left\{\dfrac{sn}{p}\right\}=\dfrac{s-1}{p}\) (which exists) to get a valid construction.

Let $a\%b$ denote the remainder when $a$ is divided by $b$. It is clear that the problem is equivalent to showing that there exist $m$ and $n$ less than some prime $p$ such that $$sm\% p<sn\% p<s$$iff $s|p-1$. This means that the residues $s, s-1, \cdots 1$ can not appear in a decreasing fashion. We will show that they are strictly decreasing iff $s|p-1$, which implies the desired conclusion. s Let $p=as+b$ where $p\% s=b$. We have the first few terms to be $$s, 2s \cdots, as, as+s-p=s-b, \cdots $$The sequence $s, s-1, s-2, \cdots$ can not appear in this order if $s-b \ne s-1$, or if $b\ne 1$, so this shows that it is only possible to have a strictly decreasing sequence if $s|p-1$. Now I will show that if $s|p-1$ we always have a decreasing sequence: let $sk=p-1$. We can easily see that our sequence becomes $$s, 2s,\cdots, ks=p-1, s-1, 2s-1, \cdots ,p-2, s-2, \cdots ,p-s$$where the first block of $k$ residues is $s, 2s, \cdots, ks$ and the following blocks of $k$ residues are one less than the corresponding terms. This means that the sequence of the leading terms of each of these $k$ blocks is $s, s-1, s-2, \cdots, 1$, which is strictly decreasing.

Remark that $\{x\} = 0$ iff $x$ is an integer, so $\left\{\frac{sm}{p}\right\}$ cannot be an integer. We show that the negation of the given condition is true iff $s\mid p-1$. Rewrite the negation of the given condition as follows: for all integers $0 < a < b < s$ with $sm\equiv a\pmod{p},sn\equiv b\pmod{p}$, we have $m>n$. Then, let $1/s\equiv t\pmod{p}$. Then, the negation of the given condition is equivalent to the statement that for all integers $0<a<b<s$ with $at\equiv m\pmod{p},bt\equiv n\pmod{p}$, we have $m>n$. Now, consider the list \[\{0t,1t,2t,\dots, st\}.\]We take $0t$ reduced modulo $p$ to be $p$ for convenience. This list is an arithmetic progression modulo $p$ with common difference $t$ that must satisfy the property that $at$ reduced modulo $p$ is larger than $bt$ reduced modulo $p$ for any $a<b$. Since $t<p$, the existence of any $a$ such that $at>kp>(a+1)t$ for some $k$ would give $(a+1)t$ reduced modulo $p$ greater than $at$ reduced modulo $p$, absurd. Thus, $0t-st\equiv p-1\pmod{p}$ must be equal to $p-1$, so $t\mid -st \mid p-1$ and thus $-st=p-1$. This implies $s\mid p-1$ as desired, so we have shown that the negation of the given existence condition holds iff $s\mid p-1$.

The problem is equivalent to showing that $$s^{-1}, 2s^{-1}, 3s^{-1}, \dots, (s-1)s^{-1}$$taken mod $p$ is strictly decreasing iff $s \mid p-1$. This is trivial$^{\mathrm{TM}}$.

I didn’t think of inverses at all somehow. The main observation is that the fractional parts are merely a distraction, and the problem is just modular arithmetic. Let $1,2, \dots, p-1$ be $a_1, a_2, \dots, a_{p-1}$ respectively. Also let $sa_1, sa_2, \dots, sa_{p-1}$ when reduced modulo $p$ be $b_1, b_2, \dots, b_{p-1}$ respectively. Claim : All $b_i \equiv{x} \mod{s}$ are “together” for all $x \in \{0, 1,2, \dots, s-1\}$ Proof. Look at the largest $b_i \equiv{x} \pmod{s}$. Let $b_i=ns+x$. Note that $$sa_i \equiv{ns+x} \pmod{p}$$$$\implies s(a_i-n) \equiv{x} \pmod{p}$$$$\implies b_{i-n} \equiv{x} \mod{p}$$After $b_{i-n}$ these keep increasing by $s$, so we’d have covered all permissible numbers with the same modulo $s$. It’s easy to prove that, if $s \mid p-1, b_1, b_2, \dots b_{p-1}$ are arranged as $s,2s, \dots, ks=p-1, s-1, \dots, sk-1) , \dots$, so if we keep a note of all these less than $s$, we see that they are arranged as $s-1, s-2, \dots, 1$. For the backward direction, we want all $b_i$s less than or equal to $s$ to be arranged as $s, s-1, s-2, \dots, 1$. Let $p=sl+r, p \leq r <s$. Now, let their be $l$ numbers in the subsequence involving $s$. Note that $a_{l+1} \equiv{sl+s} \equiv{-r} \pmod{p}$. Therefore, $b_{l+1}=p-r=p-1 \implies r=1$. Finally, we get $p=sl+1 \implies s \mid p-1 \blacksquare$

A solution for the "only if" part: Let $f(x)$ be the remainder of $sx$ in the division by $p$. It's easy to see that the problem is the same as asking for integers $m,n$ such that: $$f(m)<f(n)<s$$for $m<n$. Let $g$ be the inverse function of $f$. If there exists $a<b<s$ such that $g(a)<g(b)$, taking $m=g(a)$ and $n=g(b)$ we have $$f(g(a))=a<b=f(g(b))<s.$$Then, such $m$ and $n$ doesn't exist only when: $$g(s-1)<g(s-2)<\dots<g(2)<g(1).$$If $s\mid p-1$: We have that $s=\frac{p-1}{k}$ for some $k$. See that, for $j\leq s$, $1+jk\leq p$ and $f(1+jk)\equiv s+j(p-1)\equiv s-j\pmod{p}$, which implies that $f(1+jk)=s-j$, since $0\leq s-j<p$. Therefore, we have $g(s-j)=1+jk$ and it's easy to see that: $$g(s-1)<g(s-2)<\dots<g(1)$$and we have that if such $m,n$ exists, $s\nmid p-1$. $\blacksquare$

For any $x \in \mathbb Z$, note that $$ \left\{ \frac{sx}{p} \right\} < \frac{s}{p} \iff \left\lfloor \frac{s(x-1)}{p} \right\rfloor < \left\lfloor \frac{sx}{p} \right\rfloor $$Now for each $1 \le t \le s-1$, let $$f(t) = \left \{ \frac{sx}{p} \right\}$$where $1 \le x \le p-1$ satisfies $$ t = \left\lfloor \frac{s(x-1)}{p} \right\rfloor < \left\lfloor \frac{sx}{p} \right\rfloor $$Clearly all of $f(1),\ldots,f(s-1)$ are distinct. Our problem is equivalent to showing $\exists$ $1 \le a < b \le s-1$ with $f(a) < f(b)$ iff $s \nmid p-1$. Note that first thing is equivalent to the sequence $f(1),\ldots,f(s-1)$ being not equal to $s-1,\ldots,1$. This is easily equivalent to $f(1) = s-1$, which is clearly equivalent to $s \mid p-1$, as desired. $\blacksquare$

The condition is equivalent to $$sm \bmod p < sn \bmod p < s.$$First, suppose that $s \mid p-1$; let $p-1=ks$ for some integer $k$. Then $$(nk+1)s \equiv s+nks \equiv s-n \pmod p,$$so the residues less than $s$ form a strictly decreasing sequence in the complete residue system given by $\{sk \mid 0 \leq k \leq p-1\}$. This means if $sm < sn < s$ under modulo $p$, then $m>n$ by our conclusion, contradiction. Now, let $s \nmid p-1$. Let $k_i \equiv \frac is \pmod p$ for $1 \leq i \leq s$. Then because $k_1 - k_s \leq p-2$, it follows that there exists an index $i$ such that $$k_i - k_{i+1} \leq \frac{p-2}{s-1} < \frac{2(p-1)}s.$$For this choice of $i$, $$s(k_i - k_{i+1}) < 2(p-1) \text{ and } s(k_i - k_{i+1}) \equiv -1 \pmod p.$$So the quantity in fact equals $p-1$, which implies $s \mid p-1$, contradiction.

Beautiful proof...

Felt a bit easy, fake solve or Observe that $\left \{ \frac{x}{p} \right \} \in \{ \frac{1}{p},\frac{2}{p},...,\frac{s-1}{p} \}$ which is only possible if $x \equiv 1,2,...,s-1 \mod p$ and $s\neq 1,2$. Hence, rewrite equation as \begin{align*} &sm \equiv x \mod p \\ &sn \equiv y \mod p \\ &0<x<y<s<p\\ &n<m<p \end{align*}Is true only and only if $ s \nmid p-1$ Assume otherwise that $s \mid p-1$. Hence $\exists k \in \mathbb{N}: \frac{p-1}{s}=k$ We have $ \frac{p-1}{k}m \equiv -\frac{m}{k} \equiv x \mod p \Rightarrow m \equiv -kx \mod p$. Similarly, $ n \equiv -ky \mod p$ Observe that $-kx>-ky$ but since $m<n<p$, that is impossible, hence such $k$ should not exist. Now, we will show that $s \nmid p-1$ works. Observe that $ms \equiv 1 \mod p \Rightarrow m \equiv \frac{1}{s} \mod p$ exists since $\gcd(s,p)=1$. Note that $m \neq p-1$. Then $n \in \{m+1,m+2,...,p-1\}$ , then $sn \equiv s+1,2s+1,3s+1,...,(p-1)s+1 \mod p$.Since $(p-1)s+1> p$, there is at least one pair of residues such that $ ks+1> (k+1)s+1 \mod p$ ( basically finishes the circle and goes back to start). Since we are adding one $s$, $(k+1)s+1 <s \mod p$, which means we can choose that $n$ for such $m$ $\square$.

Mocking USAMO 2006 Day 1 result on p1: 73 minutes, 14 seconds (nub time :c) If part: $s \not \; \mid p-1$ Since $s \ne 1,2$ and $s<p$ we get $\gcd(s,p)=1$ so $\{0,s,2s,...,(p-1)s \}$ makes a complete residue system $\pmod p$. Now let $0<\ell<p$ such that $s\ell \equiv -1 \pmod p$ then note that $\{s((s-1)\ell+1),...,s(2\ell+1),s(\ell+1) \}$ makes a residue system from $1$ to $s-1$ in $\pmod p$, now since $s \not \; \mid p-1$ we get that $s\ell \ge 2p-1$ so $s\ell-\ell > p-1$ is equivalent to $2p-1>p+\ell-1$ which is true hence we get that $(s-1)\ell>p$ (as $p$ is prime so $(s-1)\ell=p$ is imposible) so now we have the existence of this constant $a$ that satisfies that its the minimun positive integer that satisfies $a\ell>p$ (it could be $s-1$ ofc), now let $a\ell+1-pm$ the residue of $a\ell+1$ in $\pmod p$ so we nee $\ell+1>a\ell+1-pm$ which is equivalent to $pm \ge p>(a-1)\ell$ but this holds becuase of the definition of $a$, now if $\ell=p-1$ we have that $s \equiv 1 \pmod p$ so $s=1$ which is not possible hence $\ell+1<p$ which means that from both facts we got it follows the existence of the $m,n$ requied in the problem thus we are done. Only if part: We already have the existence of $m,n$ Assume FTSOC that $s \mid p-1$ then let $\ell'$ such that $s\ell'=p-1$ now as $\{s((s-1)\ell'+1),...,s(2\ell'+1),s(\ell'+1) \}$ makes a residue system from $1$ to $s-1$ in $\pmod p$ and $(s-1)\ell'<s\ell'=p-1$ we have that such $m,n$ cannot exist which is a contradiction, hence $s \not \; \mid p-1$ as desired. Since we did both parts we are done

Sketch:

Note that $\left\{ \frac{sm}{p} \right\} = \frac{x}{p}$ where $x \equiv sm \pmod{p}$. Similarly $\left\{ \frac{sn}{p} \right\} = \frac{y}{p}$ where $y \equiv sn \pmod{p}$. Now assume $s \mid p - 1$. Then let $st = p - 1$. Then consider $s(t+k)$ for some $0 < k < s$. Clearly we have, \begin{align*} s(t+k) \equiv sk - k \pmod{p} \end{align*}Thus multiples of $s$ would cover the residue class modulo $p$ in the following cycles sequentially, \begin{align*} &\{s, 2s, \dots, p - 1\}\\ &\{s - 1, 2s - 1, \dots, p - 2\}\\ &\vdots\\ &\{1, s + 1, \dots, p - s\} \end{align*}From this it can clearly be observed that no valid $m$, $n$ pair exists. Now for the other direction. Assume that $s \nmid p - 1$. Then say $sk$ is the largest $k$ such that $sk < p$. Then note that if $s(k+1)$ and $s-1$ are congruent modulo $p$ we have, \begin{align*} s(k+1) &\equiv s - 1 \pmod{p}\\ sk &\equiv - 1 \pmod{p} \end{align*}which in turn would imply that $s \mid p - 1$ contradiction. Hence we can set $m = k + 1$. Then take $n$ such that $sn \equiv s - 1 \pmod{p}$ which clearly exists as $\gcd(s, p) = 1$. Also $m < n$ from our conditions so this works.

Note that $\left \{\frac{sm}{p} \right\} = \frac{r}{p}$, where $r$ is the remainder of $sm$ divided by $p$. Assume $s \mid p-1$. Then note that $s - i \equiv s(\frac{p-1}{s}i + 1)$ and whenever $i < j$, $s - i > s - j$ and $\frac{p-1}{s}i + 1 < \frac{p-1}{s}j + 1$, so it's impossible to find $0 < m < n < p$ such that $\left \{\frac{sm}{p} \right\} < \left \{\frac{sn}{p} \right \} < \frac{s}{p}$. Now assume $s \nmid p-1$. Let $0 <d < p$ be a positive integer such that $sd \equiv -1 (p)$ and let $0 < a_i < p$ be a positive integer such that $sa_i \equiv s - i (p)$. If there aren't positive integers $0 < m < n < p$ such that $\left \{\frac{sm}{p} \right\} < \left \{\frac{sn}{p} \right \} < \frac{s}{p}$, then $a_1 < a_2 < \dots < a_{s-1}$. Note that $s(a_i - a_{i-1}) \equiv -1 (p)$, so $a_i - a_{i-1} = d$. Note that $a_1 = d+1$, so $a_{s-1} = d(s-1) + 1 \equiv -d (p)$. Combined with the fact that $a_{s-1} < p$, we see that $a_{s-1} = p-d$, which means that $sd = p-1$, a contradiction. Hence we're done. $\blacksquare$

Let $\mathbb{Z}_p$ denote the integers modulo $p$. Let homomorphism $\varphi:\mathbb{Z}\rightarrow\mathbb{Z}_p$ be given by $n\mapsto n+p\mathbb{Z}$. Let $\psi$ be the restriction of $\varphi$ to $\{0,1,\ldots,p-1\}$ so $\psi$ is a bijection. Define a total ordering $(\mathbb{Z}_p,\preceq)$ on $\mathbb{Z}_p$ as follows: \[ a\preceq b\iff\psi^{-1}(a)\leq\psi^{-1}(b). \]Note that $a\preceq b$ is equivalent to $-a\succeq -b$. We prove the following (which is equivalent to the problem): Claim. Fix $s\in\mathbb{Z}_p^\times$ and let $S:=s^{-1}\{\overline{1},\overline{2},\ldots,\overline{s-1}\}$. Call a pair $(m,n)\in S\times S$ a conflicting if either $m\prec n$ and $sm\succ sn$, or $n\prec m$ and $sn\succ sm$. Then all pairs $(m,n)$ are conflicting if and only if $\psi^{-1}(s)\mid p-1$. Proof. For $s=\overline{1}$ the statement is clearly true so assume $s\succ\overline{1}$. Note that $(m,n)$ is conflicting if and only if either $m\prec n$ and $(-s)m\prec(-s)n$, or $n\prec m$ and $(-s)n\prec(-s)m$. It is easy to see that all pairs $(m,n)$ are conflicting if and only if \[ s^{-1}\succeq-\psi\left(\left\lfloor\frac{p-1}{\psi^{-1}(s)-1}\right\rfloor\right)=:\alpha.\tag{*} \]Indeed, we must have $\psi^{-1}(s-\overline{1})\psi^{-1}(-s^{-1})\leq p-1$ since otherwise we can take the minimal $i\in\{\overline{1},\overline{2},\ldots,\overline{s-1}\}$ such that $\psi^{-1}(-s^{-1})\psi^{-1}(i)\geq p$, and take $m:=s^{-1}(i-\overline{1})$ and $n:=s^{-1}i$. Note that $i\succ\overline{1}$ so $sm\prec sn$ but \begin{align*} \psi^{-1}(-m)&=\psi^{-1}((-s^{-1})(i-\overline{1}))\\ &=\psi^{-1}(-s^{-1})(\psi^{-1}(i)-1)\\ &>\psi(-s^{-1})\psi^{-1}(i)-p\\ &=\psi^{-1}((-s^{-1})i)\\ &=\psi^{-1}(-n). \end{align*} Note that $\psi^{-1}(s)\psi^{-1}(-s^{-1})=pd-1$ for some $d\in\mathbb{Z}^+$. Multiplying by $\overline{-1}$ and applying $\psi^{-1}$ to both sides of $(*)$, we get $\psi^{-1}(-s^{-1})\leq\left\lfloor\frac{p-1}{\psi^{-1}(s)-1}\right\rfloor$. Thus \[ \frac{pd-1}{\psi^{-1}(s)}\leq\frac{p-1}{\psi^{-1}(s)-1}\iff p((d-1)\psi^{-1}(s)-d)+1\leq 0, \]which occurs if and only if $d=1$. This is equivalent to $\psi^{-1}(s)\mid p-1$, as desired. $\square$