How does the proof of Fermat's little theorem work which uses inverses? I am struggling to understand the proof of Fermat's little Theorem which uses inverses.
Namely,consider the set of numbers $S=\{1,2,3,\cdots,p-1 \}$ and consider the set $a\cdot S=\{a,2a,\cdots,a(p-1)\}$ ,then if we can prove that $a \cdot S$ is distinct ,then the proof is concluded as this implies that $a\cdot S$ is a permutation of $S$.
Here I don't understand how the fact that $a\cdot S$ is distinct implies that it is a permutation of $S$ .
I've just started studying this ,so please explain it at a basic level...
 A: We know that, given $a\in S$, that $a$ has an inverse $\mod p$. Now if $ax\equiv ay\mod p$, we can multiply both sides by the inverse so that $x\equiv y\mod p$. This means that the elements off $a\cdot S$ are distinct.
We now know that $a\cdot S$ has $p-1$ distinct elements, all nonzero, so those elements must be $\{1,2,\cdots,p-1\}$, but perhaps in a different order.
But I also want to mention that in the proof for Fermat's Little Theorem, the order of those elements is irrelevant.
I hope this helped!
A: Pick any two distinct elements in $aS$, say $as_1$ and $as_2$.
$as_1 \equiv as_2 \pmod p \iff s_1 \equiv s_2 \pmod p$
beacuse we assume $a$ is invertible.
So the set $aS$ is composed by $p-1$ distinct elements in $\mathbb Z_p^*$.
But $|\mathbb Z_p^*|=p-1$
so they are just the elements of $\mathbb Z_p^*$ written in a different oreder.
A: What the author is trying to say:
If each element in $a\cdot S=\{a,2a,3a,\ldots,a(p-1)\}$ is distinct, then we know that the function $\Bbb{Z}_p\to\Bbb{Z}_p$ given by $s\mapsto as$ is a permutation.
Recall that a permutation is just a bijection from one set to itself.
To see that this is a permutation, we just have to see that the function is a bijection.
Injective: suppose $as_1=as_2$. Since every element in $a\cdot S$ is distinct, clearly $s_1=s_2$.
Surjective: pick any element in $\Bbb{Z_p}$. Since each element in $a\cdot S$ is distinct, and there are $p-1$ elements in the set, we must have each possible number in the set, so there has to be a pre-image of our number.
