Problem about proving fermat's little theorem

Question

We know that, there is an important step to prove Fermat's little theorem, two side times $(n- 1)! \cdot a^{n-1} = (a\cdot1)\cdot(a\cdot2)\cdot...\cdot(a\cdot(n-1)) \equiv (n-1)! \mod(n) $

Example:
If $\gcd(a,b)=1, x = x_1\mod (n), y = y_1 \mod (n), z = z_1 \mod (n)$, then ${a\cdot x,a\cdot y,a\cdot z} \mod n = {x,y,z}$, only the arrangement different, what is the step to prove that?

Answer 1

Note first that in Fermat's Theorem, the number you call $n$ is prime. So we change the name and call it $p$.

We want to show that if $a$ is not divisible by $p$, then the numbers $a\cdot 1, a\cdot 2,\dots, a\cdot (p-1)$ are all incongruent modulo $p$.

Suppose to the contrary that $ax\equiv ay\pmod{p}$, where $1\le x\lt y \le p-1$. Then $p$ divides $ay-ax$, that is, $p$ divides $a(y-x)$.

Since $p$ does not divide $a$, it must divide $y-x$. This is impossible, since $1\le y-x\lt p$.

Recall now that any number not divisible by $p$ is congruent modulo $p$ to one of $1,2,\dots,p-1$. Our numbers $a\cdot 1,a\cdot 2,\dots, a\cdot (n-1)$ are congruent to different numbers in the interval from $1$ to $p-1$. But there are $p-1$ numbers in our collection $a\cdot 1,a\cdot 2,\dots, a\cdot (n-1)$. So they must be congruent, in some order, to all the numbers from $1$ to $p-1$.

Answer 2

It is easy to see that if $p$ is prime and $a$ is not a multiple of $p$ then the numbers $$a,\,2a,\,\ldots,\,(p-1)a\tag{*}$$ are not multiples of $p$. Also, no two of these numbers are congruent modulo $p$: if say $ia\equiv ja\pmod p$ with $1\le i<j\le p-1$, then $$(j-i)a\equiv0\pmod p$$ with $$1\le j-i\le p-1\ ,$$ which is impossible. So the $p-1$ numbers (*) are all different and non-zero modulo $p$, so they must, in some order, be congruent to $1,2,\ldots,p-1$. Hence $$(a)(2a)\cdots((p-1)a)\equiv(1)(2)\cdots(p-1)\pmod p\ .$$ I think this is the step you are asking for.