Fermat’s Little Theorem, Euler, Wilson and CRT

Fermat’s little theorem: statement and meaning

Fermat’s little theorem turns a large power into a manageable remainder. Let p be a prime number and a an integer that is not divisible by p. Then $a^{p-1}\equiv1\pmod p$. The symbol $\equiv$ means that the two numbers have the same remainder on division by p. Equivalently, p divides $a^{p-1}-1$.

A second form is $a^p\equiv a\pmod p$ for every integer a. If p divides a, both sides have remainder zero. Otherwise multiply the first form by a. Keep the conditions with the formula: the exponent p − 1 form needs a nonzero remainder for the base.

Proof of Fermat’s little theorem using remainders

1. List the products $a,2a,3a,\ldots,(p-1)a$. None has remainder zero modulo p: a prime dividing one of these products would have to divide a or its multiplier, and neither is possible.

2. No two products have the same remainder. If $ia\equiv ja\pmod p$, then p divides $a(i-j)$. Since p does not divide a, it divides i − j. But i and j both lie from 1 to p − 1, so their difference has absolute value less than p. It must be zero.

3. We have p − 1 different nonzero remainders, so they must be precisely $1,2,\ldots,p-1$, perhaps in a different order. Multiplying them gives $a^{p-1}(p-1)!\equiv(p-1)!\pmod p$.

4. The factorial $(p-1)!$ shares no prime factor with p, so it has a multiplicative inverse modulo p. Multiply both sides by that inverse to obtain $a^{p-1}\equiv1\pmod p$. This explains why cancellation is valid; cancellation in modular arithmetic always needs justification.

The key idea is that multiplying by a number coprime to the modulus rearranges the available invertible remainders. Revisit reduced residue systems or modular inverses and congruences if either step is unfamiliar.

Example: find the remainder of a large power

Find the remainder when $7^{222}$ is divided by 13. The number 13 is prime and does not divide 7, so $7^{12}\equiv1\pmod{13}$. Now $222=12\cdot18+6$, and therefore $7^{222}\equiv7^6\pmod{13}$.

Compute in small steps: $7^2\equiv10$, $7^4\equiv10^2\equiv9$, and $7^6\equiv9\cdot10\equiv12\pmod{13}$. The required remainder is 12. Reducing after each multiplication keeps the arithmetic small.

Example: prove divisibility without expanding

Prove that $n^7-n$ is divisible by 42 for every integer n. Fermat gives divisibility by 7 directly. Modulo 2, an integer and its positive powers have the same parity. Modulo 3, either n has remainder zero, or $n^2\equiv1$, so $n^6\equiv1$ and $n^7\equiv n$. Thus 2, 3 and 7 each divide the expression. As they are pairwise coprime, their product 42 divides it.

Common questions about Fermat’s theorem

Further reading: MIT 18.310 notes on elementary algebra and the Chinese remainder theorem, including Fermat’s little theorem. The explanation and practice on this website are original teaching material.

Euler’s totient function: computing phi

For a prime power $p^{k}$, exclude the $p^{k-1}$ multiples of $p: \phi (p^{k})=p^{k}-p^{k-1}$. For 60=2²·3·5, inclusion–exclusion over its prime divisors gives φ(60)=60(1−1/2)(1−1/3)(1−1/5)=16. Only distinct prime factors appear in the product.

Wilson’s theorem: why the congruence works

For prime p, every nonzero class has an inverse. Pair each class with its inverse; each pair multiplies to 1. The self-inverse classes satisfy x²≡1, so p divides (x−1)(x+1), giving x≡±1. For odd p, the unpaired product is −1, proving (p−1)!≡−1. The prime p=2 can be checked directly. The converse follows because a composite n has a proper divisor d with 1<d<n, and d divides both (n−1)! and n; it cannot then divide (n−1)!+1.

Binomial coefficients modulo a prime

For prime p and 0<k<p, the integer C(p,k) is divisible by p. In p!/[k!(p−k)!], the numerator has one factor p and the denominator has none. Thus $(a+b)^{p}\equiv a^{p}+b^{p} \bmod p$. For example (x+1)⁵≡x⁵+1 mod 5. This conclusion can fail for composite exponents; (1+1)⁴=16 is not congruent to 1⁴+1⁴=2 modulo 4.

Chinese remainder theorem: compatibility and examples

The pair x≡1 mod 4, x≡3 mod 6 is compatible because both residues are odd. The solutions are x≡9 mod 12: check x=1,5,9 among residues 1 mod 4. In contrast x≡0 mod 4 and x≡1 mod 6 is impossible because the parity requirements conflict. With non-coprime moduli, do not multiply moduli and assume unique residues automatically.

Carmichael’s exponent: an advanced extension

The Carmichael function λ(n) is the least positive exponent L such that $a^{L}\equiv 1 \bmod n$ for every a coprime to n; set λ(1)=1 by convention. Euler’s theorem ensures such an exponent exists. For odd prime powers $\lambda (p^{k})=\phi (p^{k})$. For powers of two, λ(2)=1, λ(4)=2 and $\lambda (2^{k})=2^{k-2}$ for k≥3. For coprime prime-power factors, take the lcm of their λ values. Thus λ(15)=lcm(2,4)=4, although φ(15)=8. These general formulas are stated here as advanced tools; verify the small example directly on the eight units modulo 15.

Digit arguments are modular arguments

In base b, b≡1 mod b−1 and b≡−1 mod b+1. Consequently the ordinary digit sum and the alternating digit sum preserve the corresponding residues. Read the base-notation lesson for a full derivation and conversion examples.