Question 190
Let $p$ be a prime number and let $a_1, a_2, \dots, a_k$ be distinct integers chosen from $1, 2, \dots, p-1$. For $1 \le i \le k$, let $r_i^{(n)}$ denote the remainder of the integer $n a_i$ upon division by $p$, so $0 \le r_i^{(n)} \lt p$. Define
$$
S = \{ n : 1 \le n \le p-1,\ r_1^{(n)} \lt \dots \lt r_k^{(n)} \}.
$$
Show that $S$ has less than $\frac{2p}{k+1}$ elements.
$$
S = \{ n : 1 \le n \le p-1,\ r_1^{(n)} \lt \dots \lt r_k^{(n)} \}.
$$
Show that $S$ has less than $\frac{2p}{k+1}$ elements.