Fermat's little theorem

Let’s dive into Fermat’s Little Theorem (FLT) :

---

1. What it says

If $p$ is a prime number and $a$ is an integer not divisible by $p$, then:

$$a^{p-1} \equiv 1 \pmod{p}$$

This means that when you raise $a$ to the power $p-1$ and divide by $p$, the remainder is 1.

---

2. A slightly different but equivalent form

Sometimes it’s written as(a is any integer but p has to be prime):

$$a^{p} \equiv a \pmod{p}$$

This form works even if $a$ is divisible by $p$.
(You can get it by multiplying the first form by $a$.)

---

3. Step-by-step example

Example 1:
Let $p = 7$ (prime), $a = 3$ (not divisible by 7).
FLT says:

$$3^{7-1} = 3^6 \equiv 1 \pmod{7}$$

Let’s check:
$3^6 = 729$
$729 \div 7 = 104$ remainder 1 ✅

---

Example 2:
$p = 5$, $a = 2$:
FLT: $2^{5-1} = 2^4 \equiv 1 \pmod{5}$
$2^4 = 16$, $16 \div 5$ remainder 1 ✅

---

Example 3 (alternate form):
$p = 11$, $a = 8$
FLT (alt form): $8^{11} \equiv 8 \pmod{11}$
Let’s check: $8^{11}$ is huge, but modular arithmetic shortcuts show
$8^{10} \equiv 1 \pmod{11}$, so multiply both sides by $8$ ⇒ $8^{11} \equiv 8$ ✅

---

4. Why it’s useful

• Primality testing: It’s the basis for some fast prime tests (like the Fermat primality test — although there are exceptions called Carmichael numbers).

• Modular inverses: If $a^{p-1} \equiv 1 \pmod{p}$, then $a^{p-2}$ is the inverse of $a$ modulo $p$.

• Cryptography: Powers mod $p$ appear all over RSA, Diffie–Hellman, and elliptic curve cryptography.

---

Proof:

Here’s the elegant proof of Fermat’s Little Theorem using the “multiply all the numbers” trick.

---

Proof (for $p$ prime, $a$ not divisible by $p$)

1. Start with the set of numbers:

$$1, 2, 3, \dots, p-1$$

These are all the positive integers less than $p$.

---

2. Multiply each by $a$:

$$a \cdot 1,\ a \cdot 2,\ a \cdot 3,\ \dots,\ a \cdot (p-1)$$

Since $p$ is prime and $a$ is not divisible by $p$, multiplying by $a$ just rearranges these numbers modulo $p$.
That is, $a \cdot 1, a \cdot 2, \dots, a \cdot (p-1)$ are all distinct mod $p$ and are just a permutation of $1, 2, \dots, p-1$.

---

3. Take the product of all the terms (mod $p$):

On one hand:

$$(a \cdot 1) \cdot (a \cdot 2) \cdot \dots \cdot (a \cdot (p-1)) = a^{p-1} \cdot (1 \cdot 2 \cdot \dots \cdot (p-1))$$

On the other hand, since it’s just a rearrangement:

$$(a \cdot 1) \cdot (a \cdot 2) \cdot \dots \cdot (a \cdot (p-1)) \equiv 1 \cdot 2 \cdot \dots \cdot (p-1) \pmod{p}$$

---

4. Cancel the factorial part:
   The product $1 \cdot 2 \cdot \dots \cdot (p-1)$ is not divisible by $p$, so it has a multiplicative inverse modulo $p$.
   Cancelling it from both sides gives:

$$a^{p-1} \equiv 1 \pmod{p}$$

✅ This is exactly Fermat’s Little Theorem.

---

Detailed explanation of step 2 above:

---

Step 2: Why $a \cdot 1, a \cdot 2, \dots, a \cdot (p-1)$ are all distinct mod $p$

We’re working modulo $p$, where $p$ is prime and $a$ is not divisible by $p$.
We want to show that if

$$a \cdot i \equiv a \cdot j \pmod{p}$$

then $i \equiv j \pmod{p}$.

---

Reasoning:

1. $a \cdot i \equiv a \cdot j \pmod{p}$ means:

$$p \ \text{divides} \ a(i - j)$$

2. Since $p$ is prime, if $p$ divides the product $a(i - j)$, then $p$ must divide either $a$ or $i - j$.

3. But $a$ is not divisible by $p$ (that’s an assumption of the theorem),
   so the only option is that $p$ divides $i - j$.

4. And because $1 \le i, j \le p-1$, the difference $i - j$ is between $-(p-2)$ and $p-2$, so the only way $p$ divides $i - j$ is if $i - j = 0$, i.e.:

$$i = j$$

---

Conclusion:
Multiplying by $a$ modulo $p$ doesn’t make any two numbers “collapse” into the same remainder — it just reorders them.

That’s why $a \cdot 1, a \cdot 2, \dots, a \cdot (p-1)$ are a permutation of $1, 2, \dots, p-1$ in mod $p$ land.

---