The probabilistic method exercise 2.7.4

Question

This is exercise 2.7.2 of the book "the probabilistic method".

Suppose $p>n>10m^2$, with $p$ prime, and let $0<a_1<a_2<...<a_m<p$ be integers. Prove that there is an integer $x$, $0<x<p$, for which the $m$ numbers $(xa_i(\mod p))\mod n$, $1 \le i \le m$ are pairwise distinct.
And I think this problem in this way. Let $\chi_x$ be the indicator for the event that the m numbers $(xa_i(\mod p))\mod n$ are pairwise distinct. Then $P(\chi_x) = \frac{n\choose m}{n^m}$, The the expected number of $(xa_i(\mod p))\mod n$ are pairwise distinct is $\sum E[\chi_x] = (p-1)\frac{n\choose m}{n^m} > \frac{(\frac{n}{m})^m}{n^{m-1}} = \frac{n}{m^m}$. Obviously, this way can not get the result that the expected number is greater than 1. Could anyone help about this problem?

Answer 1

I got an answer about this problem but I don't know if it is right.
For any $a_i,a_j$,let $A_x$ denote the event that $(xa_i(\mod p))\mod n = (xa_j(\mod p))\mod n$, then $P_r(A_x) = \frac{1}{n}$. The probability that all m numbers are pairwise distinct is $(1-\frac{1}{n})^{m \choose 2}$. Then the expected number of x is $(p-1)(1-\frac{1}{n})^{m \choose 2} \ge (10m^2 - 1)(1-\frac{1}{10m^2})^{\frac{1}{2}m(m-1)} \ge (10m^2 - 1)(1-\frac{\frac{1}{2}m(m-1)}{10m^2}) \ge 10m^2-1-\frac{1}{2}m^2 + \frac{1}{2}m > 1$, which yields the result when $m \ge 1$.

Answer 2

Below is my solution when I met the problem in homework before.

Choose integer $x$ uniformly and randomly in $[p-1]$, clearly, with the assumptions, for each $i$, $(xa_i\ \mathrm{mod}\ p)$ is distinct in $[p-1]$. Let $X$ be the random variable denoting the number of ordered pairs $(i, j)$, where $i, j \in [m]$ and $i \neq j$, which is naturally the sum of indicator random variables $X_{ij}$ for all possible $(i, j)$, where $X_{ij}$ indicates $(xa_i\ \mathrm{mod}\ p)\ \mathrm{mod}\ n = (xa_j\ \mathrm{mod}\ p)\ \mathrm{mod}\ n$. Thus, \begin{align*} E[X] & = \sum_{i \neq j} X_{ij} \\ & \leq \sum_{i} \sum_{j \neq i} \frac{\lfloor \frac{p-1}{n} \rfloor}{p-1} \\ & \leq \sum_{i} \sum_{j \neq i} \frac{1}{n} \\ & = \frac{m(m-1)}{n} \\ & < \frac{m(m-1)}{10m^2} \\ & < \frac{1}{10}, \end{align*}
which implies for some $x$, $X = 0$, i.e., $(xa_i\ \mathrm{mod}\ p)\ \mathrm{mod}\ n, 1 \leq i \leq m$ are pairwise distinct, completing the proof.