Fermat's Little Theorem

Fermat's Little Theorem

If $p$ is prime and $a$ is not divisible by $p$, then: $a^{p-1} \equiv 1 \pmod{p}$

Equivalently, for any integer $a$: $a^p \equiv a \pmod{p}$

Examples

• $2^6 \equiv 1 \pmod{7}$ (since 7 is prime, $\gcd(2,7)=1$)
• $3^{10} \equiv 1 \pmod{11}$
• $5^4 \equiv 1 \pmod{5}$? No! $\gcd(5,5) \neq 1$

Proof Sketch

Consider the set $\{a, 2a, 3a, \ldots, (p-1)a\} \pmod{p}$.

These are all distinct and non-zero (since $\gcd(a,p) = 1$).

So they're a permutation of $\{1, 2, \ldots, p-1\}$.

$a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p}$ $a^{p-1} (p-1)! \equiv (p-1)! \pmod{p}$ $a^{p-1} \equiv 1 \pmod{p}$

(We can divide by $(p-1)!$ since $\gcd((p-1)!, p) = 1$.)

Applications

Computing Modular Inverses

If $p$ is prime and $\gcd(a,p) = 1$: $a^{-1} \equiv a^{p-2} \pmod{p}$

Reducing Large Exponents

$a^k \pmod{p}$ where $k$ is huge: $a^k \equiv a^{k \mod (p-1)} \pmod{p}$

Example

Compute $3^{100} \pmod{7}$: $100 = 6 \times 16 + 4$ $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 81 \equiv 81 \equiv 4 \pmod{7}$

Euler's Theorem (Generalization)

For any positive integer $n$ and integer $a$ with $\gcd(a, n) = 1$: $a^{\phi(n)} \equiv 1 \pmod{n}$

where $\phi(n)$ is Euler's totient function.

Euler's Totient Function

$\phi(n)$ = count of integers from 1 to $n$ coprime to $n$.

Computing $\phi(n)$

For prime $p$: $\phi(p) = p - 1$

For prime power $p^k$: $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$

Multiplicative property: If $\gcd(m, n) = 1$: $\phi(mn) = \phi(m)\phi(n)$

General formula: For $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$: $\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$

Examples

$\phi(10) = 10 \cdot \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 10 \cdot \frac{1}{2} \cdot \frac{4}{5} = 4$ The numbers coprime to 10: 1, 3, 7, 9.

$\phi(12) = 12 \cdot \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4$

Properties of $\phi(n)$

$\sum_{d \mid n} \phi(d) = n$

The divisors of $n$ partition $\{1, 2, \ldots, n\}$ by gcd with $n$.

Fermat as Special Case of Euler

When $n = p$ (prime): $\phi(p) = p - 1$

So Euler's theorem becomes Fermat's theorem.

Carmichael Numbers

A Carmichael number is a composite $n$ such that: $a^{n-1} \equiv 1 \pmod{n}$ for all $a$ coprime to $n$.

Examples

561, 1105, 1729, ...

These "fool" the Fermat primality test.

Detection

Carmichael numbers are square-free with at least 3 prime factors.

Order of an Element

The order of $a$ modulo $n$ is the smallest positive $k$ such that: $a^k \equiv 1 \pmod{n}$

Written $\text{ord}_n(a)$.

Properties

• $\text{ord}_n(a)$ divides $\phi(n)$
• $a^m \equiv 1 \pmod{n}$ iff $\text{ord}_n(a) \mid m$

Primitive Roots

$g$ is a primitive root mod $n$ if $\text{ord}_n(g) = \phi(n)$.

Primitive roots exist for: $n = 1, 2, 4, p^k, 2p^k$ (where $p$ is odd prime).