Fermat, Euler & Orders

Fermat’s Little Theorem

If $p$ is prime and $\gcd(a,p)=1$:

An equivalent form that works even when $p \mid a$: $a^p \equiv a \pmod p$.

Euler’s theorem

Euler’s theorem generalizes Fermat’s to any modulus, not just primes, using Euler’s totient function $\varphi(m)$ (the count of integers from 1 to $m$ that are coprime to$m$):

For a prime $p$, $\varphi(p) = p-1$, recovering Fermat’s theorem as a special case.

Multiplicative order

The order of $a$ modulo $m$ is the smallest positive integer $k$ such that $a^k \equiv 1 \pmod m$. The order always exists when $\gcd(a,m)=1$, and — this is the key structural fact — the order always divides $\varphi(m)$, and more generally divides any exponent $n$ for which $a^n \equiv 1 \pmod m$. This is often the fastest way to find an exponent cycle length: it must be a divisor of $\varphi(m)$, so you only need to test those divisors rather than every possible length.

Practice problems