Partial part of fermat's little theorem

Question

Am I fool? I cannot understanding the partial part of the proof.

$\{1,2,...,p-1\}\equiv \{a,2a,...,(p-1)a\}\ (mod\ p)$

Why above statement is true? How I remove a??

Answer 1

Hint: If $a \not\equiv 0 \bmod p$, then the map $x \mapsto xa$ is injective on the nonzero classes mod $p$.

Answer 2

All of the members of the first set, being smaller than $p$, are their own residues $\mod{p}$. Then there is a step that proves if you multiply any member of the first set by a constant such as $a$ (which is relatively prime to $p$), you get a unique value $\mod{p}$.

So by the pigeonhole principle, there are $p-1$ distinct elements after multiplying all of the first set of elements by $a$, and since they are distinct, they must correspond to the elements in the first set, although not necessarily in the same order.

Next, you don't get rid of $a$, rather you multiply all of the elements in the first set to get a first product, and all of the elements of the second set to get a second product, with the result that the two products are congruent $\mod{p}$.

The first product is $(p-1)!$ and the second set is $(p-1)!\cdot a^{p-1}$. Since $(p-1)!$ is relatively prime to $p$, it can be divided out of each side of the equivalence to leave the desired relationship, $1\equiv a^{p-1}\mod{p}$.