Arithmetic progressions in multiples of $a \mod p$

Question

Fix a prime number $p$ and consider integers $0<a,b<p$. Prove that from remainders of $a,2a,3a,\cdots, ba \mod p$ you can choose $\lfloor{\sqrt{b}}\rfloor$ numbers that when put in increasing order form arithmetic progression.

Here is my attempt:
The remainders will be of the form

$a,2a,\cdots,ka,$

$(k+1)a-p,\cdots,k_1a-p$

$(k_1+1)a-2p,\cdots,k_2a-2p$

and so on. Each row will have either $k$ or $k+1$ elements so if $k+1\geq\lfloor{\sqrt{b}}\rfloor$ then we can just choose that row as our arithmetic progression. So suppose that $k+1<\lfloor{\sqrt{b}}\rfloor$ then we will have more then $\lfloor{\sqrt{b}}\rfloor$ rows. Now we could try to choose a arithmetic progression starting in the top row and setting the difference to either $ka-p$ or $(k+1)a-p$. This would correspond to going down or left/right and down in the table, depending on the length of the row. I couldn't really get this approach to work any further.

I would really appreciate solution or any hints.

Answer 1

Notation: Let $ \{ x \} $ denote the remainder when $x$ is divided by $p$.

Let $ \lfloor \sqrt{ b} \rfloor = c$.

Claim:

One of the $c$ values $\{a\}, \{2a\}, \ldots , \{ca\}$ is either $< \frac{p}{c} $ or $ > \frac{(c-1)p}{c}.$

Proof:

By contradiction. Suppose that none of them satisfy the condition. Then by Pigeonhole Principle applied to these distinct $c$ values as pigeons and the $c-2$ ranges

$$ ( \frac{p}{c}, \frac{2p}{c}), ( \frac{2p}{c}, \frac{3p}{c}), \ldots , ( \frac{(c-2)p}{c}, \frac{(c-1)p}{c}) $$

as holes, then at least 2 of these values lie in the same hole.
Let $n_1 > n_2$ and $ \{ n_1 a \}, \{ n_2 a \}$ lie in the same hole.
Then $ | \{n_1a\} - \{n_2 a\} | < \frac{ p}{c}$, and so $\{ (n_1 - n_2) a \}$ is either $< \frac{p}{c}$ or $> \frac{(c-1)p}{c}$, as desired.

Note that we have to take the "larger index minus the smaller index" to ensure that $ n_ 1 - n_2 > 0 $ is one of the $c$ values.

Corollary:

First case: If $\{na\} < \frac{p}{c}$ with $0 < n \leq c$, then $\{na\}, \{2na\}, \{3na\}, \ldots \{cna\}$ is a sequence of $c$ terms that form an increasing arithmetic progression (in that order).

Second case: if $\{na\} > \frac{(c-1)p}{c}$ with $0 < n \leq c$, then $\{na\}, \{2na\}, \{3na\}, \ldots \{cna\}$ is a sequence of $c$ terms that form a decreasing arithmetic progression (in that order).

Notice that $ cn \leq c^2 \leq b$, so we do indeed have $c$ terms.

---

Notes:

1. Notice that we could force the indices to be of the form $n, 2n, \ldots cn$, and the remainders to be properly sorted. Though, stating this in the question would have given away too much for an Olympiad problem.
2. The first case of "terms are of the form $na, 2na, 3na, \ldots$ and the remainders are of the form $r, 2r, 3r, \ldots$" was easy to observe. It was wishful thinking that this always existed.
3. When playing with $p = 17, b = 9, a = 7$, I couldn't find any that fit the first case. I then realized that the sequence $\{14\}, \{28\}, \{42\} = 14, 11, 8$ was a good match for what I wanted, which gave the second case. This choice led to "the indices are of the form $n, 2n, \ldots cn$ and the remainders are arranged in order".
4. For this set of $p,a,b$, there are other arithmetic progressions like $\{7\}, \{21\},\{35\} = 7, 4, 1$. This choice would have led to "the indices form an arithmetic progression and the remainders are arranged in order". There were no other arithmetic progressions, so it's safe to guess that one of these patterns must work.
5. The condition that $p$ is prime is used to ensure that the remainders are distinct. In particular, we could have relaxed the condition to $ 1 = \gcd(a, p) = \gcd (b, p) $ instead.