Number Theory
Advanced

Fermat's Little Theorem

Holds when p is prime and gcd(a,p)=1.

Formula

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

Variables

aInteger
pPrime

Example

For p = 5, a = 2: 2⁴ = 16 ≡ 1 (mod 5). ✓

Did You Know?

Fermat's little theorem is a workhorse of primality testing and the RSA encryption that secures the web.

fermatprimemodular