Understanding One of Fermat's little theorem's proof Fermat's Little theorem :
Let $p$ be a prime which does not divide the integer $a$, then $a^{p-1} \equiv 1 (\mod p)$.
Leibniz's proof


*

*suppose that $ra$ and $sa$ are the same modulo $p$, then $r \equiv s (\mod p)$. {So the first p-1 multiples of a are distinct and non zero}. 

*Therefore $a, 2a, 3a, ... (p-2)a, (p-1)a$ must be congruent to $1, 2, 3, ... p-2, p-3$ in some order

*Multiply all these congruences we get $a^{p-1}(p-1)! \equiv (p-1)! (\mod p)$

*Divide by $(p-1)!$ on both sides we get $a^{p-1} \equiv 1 (\mod p)$
My issues with a full understanding of the proof
The text I've put in between brackets {} are the parts of the proof I haven't understood


*

*first brackets: {So the first p-1 multiples of a are distinct and non zero}. Isn't that implied in the statement of the proof? Why is that part of the proof necessary?


What is the proof that the first $p-1$ multiples of $a$ will necessarily be congruent to 1, 2 ... p-1 in some order?

Because if $ak \equiv 0 \pmod{p}$, for some $1 \leq k \leq p-1$, then $p \mid ak$. But, by Euclid's Theorem, as $\gcd(p,k) = 1, p \mid a$, a contradiction.
Therefore, $ak \not\equiv 0 \pmod{p}$, for all $1 \leq k \leq p-1$. Then we've got $p-1$ distinct possible values of $k$. Since that, for every $k$ there must be a unique $r \in \{1,\ldots,p-1\}$ so that $ak \equiv r \pmod{p}$.
