# 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:

1. Why is it true that $\gcd ((p-1)!, p)= 1$?
2. Why can we infer that $a^{p-1} \equiv 1$?
• for the frist question: if $p$ is prime then observe than $(p-1)!$ doesnt contain $p$ as a factor, hence $\gcd((p-1)!,p)=1$ – Masacroso Mar 19 '17 at 15:44
• And for the second question, you can always write the $gcd(a,b)$ as a linear combination of $a$ and $b$ with integer coefficients (this is from the Euclidean algorithm). Use this to show that if some number is relatively prime to $p$, then it has a multiplicative inverse mod $p$. – Malkoun Mar 19 '17 at 15:46
• Fermat's little theorem en.wikipedia.org/wiki/Fermat%27s_little_theorem?wprov=sfla1 – Zuo Mar 19 '17 at 15:51

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$

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

• The last statement is essentially my question. Why does the fact $p\not\vert (p-1)!$ implies that you can cancel $(p-1)!$ from both sides? – OliOliver Mar 19 '17 at 16:14
• It doesn't essentially imply that $(p-1)!$ is being cancelled because of that property. It merely states that they are relatively prime to each other and, hence, we can use the property of modular arithmetic to basically remove $(p-1)!$ as if it of no use here(as we are dealing with, say, modulo $p$ and not modulo $(p-1)!$) and appears on both sides leaving it to be factored out. – HKT Mar 19 '17 at 16:25
• Carefully think about it. Suppose if $p|(p-1)!$, we would have been left with $0 \pmod p$ on the right hand side. I hope that helps. – HKT Mar 19 '17 at 16:28
• You are just over-thinking it. I assure you once you get the hang of it and review the basic modular arithmetic definitions and get a stronger grasp on the notation, there will be clarity. – HKT Mar 19 '17 at 16:30

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 might as well just write $ax\equiv b\bmod m\implies x=a^{-1}b\bmod m$ when $\gcd(a,m)=1$. No need to overcomplicate it. – arctic tern Mar 19 '17 at 15:55
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$$