Why $1\equiv a^{p-1} \mod p$?

Question

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:

1. Why is it true that $\gcd ((p-1)!, p)= 1$?
2. Why can we infer that $a^{p-1} \equiv 1$?

Answer 1

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

2. 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$

Answer 2

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.

Answer 3

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

Answer 4

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