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$?

 A: 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$.
A: If you write down $(p-1)!$ as $(p-1)\cdot(p-2)\cdot\cdot\cdot1$ you can easily notice that $p$ and $(p-1)!$ have no common factors. 
So $gcd((p-1)!,p) = 1$.
Now, knowing that:
$$ax \equiv b \mod(m) \implies x \equiv b \cdot a^{-1}  \mod(\frac{m}{gcd(m,a)})$$
you have the answer to your question.
A: *

*The only divisors of $p$ are $p$ and $1$. What are the divisors of $(p-1)!$?

*Once you know that $p, (p-1)!$ are relatively prime, consider $(p-1)! * (a^{p-1} - 1) \equiv 0 \mod p$. The relative primeness tells you that this is only possible if $(a^{p-1} - 1) \equiv 0 \mod p$
A: For the first question, take, for example, $p = 7$.  Then $(p-1)! = 2\cdot3\cdot4\cdot5\cdot6 = 2^4\cdot3^2\cdot5$.  Notice that in the first equation all of the factors are strictly less than $p = 7$, which implies that all of the prime factors are also strictly less than $p$.  Since $p$ is prime, this means that $p$ and $(p-1)!$ can have no prime factors in common.
Now this implies Fermat's little theorem because, having shown that $(p-1)!$ is relatively prime with $p$, we can apply the cancellation law.
Whenver $\gcd(a,m) = 1$, 
$$ax \equiv ay \mod m$$
$$\downarrow$$
$$x \equiv y \mod m$$
