# Why does fermat little theorem work?

I'm trying to understand intuitively why (p-1)th power of any integer(not divisible by p) leaves a remainder of 1 when divided by p. (where p is a prime number)

I understand that p times any integer becomes a multiple of p and would be divided p. Similarly, can I understand the growth of the exponential function and reason why p-1 th power of any integer is always congruent to 1 mod p.

• Firstly, it's not any integer. It's only integers not divisible by $p$. Secondly, you might want to understand the variant of Fermat's little theorem which says that $a^p\equiv a\pmod p$ (which does work for all $a$. This one can be seen easily from the formula $(a+b)^p\equiv a^p+b^p\pmod p$, which follows from binomial expansion, and induction. Sep 12, 2019 at 12:03
• primes.utm.edu/notes/proofs/FermatsLittleTheorem.html
– user645636
Sep 12, 2019 at 12:06
• Seconding @Wojowu. Binomial theorem is your friend here. Show it for $a = 1$ then for the induction hypothesis assume it holds for $k$ then prove for $k+1$ with binomial theorem. There is a secondary result built into this that you need which is that $p$ divides $\binom{p}{m}$ for any $0< m < p$ where $p$ is prime. Primality is key here and it's used in a subtle way. Sep 12, 2019 at 12:06
• you need nothing but the fact that the multiples of a are coprime to p as in the proof in my link.
– user645636
Sep 12, 2019 at 12:09
• @RoddyMacPhee That's a very nice way to do it. Definitely one of the cuter proofs I've seen for a simply-stated result. Sep 12, 2019 at 12:11

Your intuition to understand this result by analogy to a multiple of $$p$$ being divisible by $$p$$ will not work in this case. The standard explanation runs like this: For any number $$a$$ which is not divisible by $$p$$, we know that $$a\equiv A \bmod p$$ where $$1\le A \le (p-1)$$. Next, we look at the products $$1\cdot A,\ 2\cdot A,\ 3\cdot A,\dots (p-1)\cdot A$$. There are $$(p-1)$$ such products, and none of them have any factors of $$p$$.

We look at those products and ask if any two of them can have the same value $$\bmod p$$. The answer is no, because if they did their difference would have to be $$0\bmod p$$. That is, $$c_2\cdot A-c_1\cdot A \equiv 0 \bmod p \iff c_2=c_1$$ and that is not the case. We have $$(p-1)$$ distinct products having values between $$1$$ and $$(p-1)$$, so by the pigeonhole principle, each value must occur once. We don't know which product corresponds to which value, but we don't need to.

We simply multiply the residues of the products $$1$$ through $$(p-1)$$ to obtain $$(p-1)!$$, and then products $$1\cdot A$$ through $$(p-1)\cdot A$$ themselves to obtain $$(p-1)!A^{p-1}$$, keeping in mind that these two numbers will be equivalent $$\bmod p$$, viz $$(p-1)!\equiv (p-1)!A^{p-1} \bmod p$$

Since $$(p-1)!$$ is coprime to $$p$$, we can divide through to remove it leaving the desired result $$1\equiv A^{p-1}\equiv a^{p-1} \bmod p$$

For example, $$a = 10$$, $$p = 7$$. We see that $$10^6 = 1000000$$ and 999999 divided by 7 is 142857.

But let's work through this example using smaller numbers. Obviously $$10^2 = 100$$. But 98 is a multiple of 7, which means that $$10^2 \equiv 2$$ $$\pmod 7$$. And 10 itself is $$3 \pmod 7$$, so we can calculate $$10^3 \equiv ?$$ $$\pmod 7$$ as $$2 \times 3 = 6$$. And then $$10^4 \equiv 6 \times 3 \equiv 4 \pmod 7$$. Next we have $$10^5 \equiv 4 \times 3 \equiv 5 \pmod 7$$.

Lastly, $$10^6 \equiv 5 \times 3 \equiv 1 \pmod 7$$, which we had already confirmed. I chose this example because $$10^n$$ modulo 7 takes on every value from 0 to 6 except 0. That's not always the case, but it helps to show which values can't be taken on.

Now consider instead $$p = 14$$, which is clearly not prime, and $$a$$ the same as before. You might be aware of the fact that 14 is not a Fermat pseudoprime. But much more importantly in this example, $$\gcd(10, 14) = 2$$, so we will see that $$10^{13} \not\equiv 1 \pmod{14}$$.

Then we see that $$10 \equiv 10 \pmod{14}$$, which is obvious but needs to be said, because $$10^2 \equiv 2 \pmod{14}$$ just the same as modulo 7. Then $$10^3 \equiv 6 \pmod{14}$$, $$10^4 \equiv 4 \pmod{14}$$, $$10^5 \equiv 12 \pmod{14}$$, $$10^6 \equiv 8 \pmod{14}$$, $$10^7 \equiv 10 \pmod{14}$$, $$10^8 \equiv 2 \pmod{14}$$... whoa, we're back to 2.

The common divisor between 10 and 14 is 2, which means that odd numbers (coprime to 2) can't occur in $$10^n \equiv ? \pmod{14}$$.

I hope this helps you understand. You might also want to work through examples where $$p$$ is composite but nonetheless coprime to $$a$$. Probably hold off on numbers like 341, 561 for now, though.