Question 36
Given a prime number $p \gt 3$ and an integer $x$, we denote by $r(x) \in \{0,1,..., p-1\}$ the remainder of $x$ modulo $p$. Let $x_1, x_2,..., x_k$ ($2 \lt k \lt p$) be integers that are pairwise distinct modulo $p$ and not divisible by $p$.
We say that a number $a \in \{1,2,..., p-1\}$ is good if:
$$
r(ax_1) \lt r(ax_2) \lt \dots \lt r(ax_k).
$$
Prove that there are at most $\frac{2p}{k+1}-1$ good numbers.
We say that a number $a \in \{1,2,..., p-1\}$ is good if:
$$
r(ax_1) \lt r(ax_2) \lt \dots \lt r(ax_k).
$$
Prove that there are at most $\frac{2p}{k+1}-1$ good numbers.