Statement#

Prove Fermat's Little Theorem:

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

Required Topics#

• Prime numbers
• Modular arithmetic
• Congruences
• Multiplicative properties
• Permutations

Definitions#

Congruence modulo p: $a \equiv b \pmod{p}$ means $p \mid (a-b)$.

Relatively prime: $\gcd(a,p) = 1$ (which is automatic when $p$ is prime and $p \nmid a$).

Strategy#

1. Consider the set $S = \{a, 2a, 3a, \ldots, (p-1)a\}$
2. Show all elements of $S$ are distinct modulo $p$
3. Therefore, $S \equiv \{1, 2, 3, \ldots, p-1\} \pmod{p}$ (as sets)
4. Take the product of all elements
5. Simplify to get the result

Corollary#

For any integer $a$ and prime $p$: $a^p \equiv a \pmod{p}$

Solution#

Solution coming soon.