Prove if $(a,p)=1$, then $\{a,2a,3a,...,pa\}$ is a complete residue system modulo $p$. [duplicate]

Solution 1:

$$k_1a \equiv k_2a \pmod p \iff p \ | \ (k_1 - k_2)a \iff p \ | \ (k_1 - k_2)$$

Since in our case $k_1, k_2 \in A = \{1, 2, ..., p\}$ we have that $\left| { k_1 - k_2} \right| \lt p $ and $p$ will not divide $(k_1 - k_2)$ if both elements are from $A$. So for any two elements $r, q \in A \;\; rp \not \equiv qp \pmod p $. Which says that every element in $\{a,2a,3a,...,pa\}$ is not congruent to each other modulo $p$. Then each of them must be distinct modulo $p$. Since we have $p$ elements in the set it forms a complete set of residues modulo $p$.

Solution 2:

${\rm mod}\ p\!:\ f(x) = x^p\!-x \equiv(x\!-\!1)(x\!-\!2)\cdots(x\!-\!p)\, $ by $\,f\,$ has roots $\,1,\ldots,p,\,$ by little Fermat.

Thus $\ \ (a^{-1}x)^p\!-a^{-1}x \equiv (a^{-1}x\!-\!1)(a^{-1}x\!-\!2)\cdots(a^{-1}x\!-\!p)\,\ $ by $\,\ x\mapsto a^{-1}x$

Thus we infer $\ \ x^p-x\equiv (x\!-\!a)(x\!-\!2a)\cdots(x\!-\!pa)\ $ by multiply LHS by $\,a,\,$ RHS by $\ a^p\equiv a$

Therefore $ \{1,2,\ldots,p\}\equiv \{a,2a,\ldots,pa\},\,$ both being all roots of $\,f(x)\,$ in the field $\,\Bbb Z/p$.