Why $1\equiv a^{p-1} \mod p$? Let $\mathbb{Z}_p^*$, where $p$ is prime and let $a\in\mathbb{Z}_p^*$.
Consider the following equation:$$(p-1)! \equiv (p-1)! a^{p-1} \mod p$$
I've read that since $\gcd((p-1)!, p) = 1$ we can infer that $$a^{p-1} \equiv 1$$
So I have two questions:


*

*Why is it true that $\gcd ((p-1)!, p)= 1$? 

*Why can we infer that $a^{p-1} \equiv 1$?


This common result is known as Fermat's Little Theorem. I hope this simple proof helps:
Consider the sequence of integers $n,2n,3n,…,(p−1)n$.
Note that none of these integers are congruent modulo $p$ to the others.
If this were the case, we would have $an≡bn \pmod p$ for some $1≤a<b≤p−1$.
Then as $gcd(n,p)=1$, and we can cancel the $n$, we get $a≡b \pmod p$ and so $a=b$.
Also, since $p∤n$ and $p∤c$, for any $1≤c≤p−1$, then by Euclid's Lemma $p∤cn$ for any such $cn$, which means $cn≢0 \pmod p$.
Thus, each integer in the sequence can be reduced $modulo \ p$ to exactly one of $1,2,3,…,p−1$.
So ${1,2,3,…,p−1}$ is the set of Reduced Residue System $modulo \ p$.
So, upon taking the product of these congruences, we see that $n×2n×3n×⋯×(p−1)n≡1×2×3×⋯×(p−1) \mod p$.
This simplifies to $n^{p−1}×(p−1)!≡(p−1)! \pmod p$.
Since $p∤(p−1)!$, we can cancel $(p−1)!$ from both sides, leaving us with $n^{p−1}≡1 \pmod p$.
