Skip to content
Axiomatic Wiki

WTFermat's little theorem

Theorem·T63

For a prime p, a to the p is congruent to a mod p, and a to the p minus 1 is congruent to 1 when p does not divide a.

Let be prime and . Then and if moreover , then , where (L80); powers from D119.
In words
For a prime p, any a raised to the p is congruent to a modulo p; and if p does not divide a, a raised to p minus 1 is congruent to 1 modulo p.
Rests onF02F03F04F05F06F08F09F11F12F13F14A01A02A06A08
Never needed: F10 · A03 · A04 · A05 · A07 · A09 (computed from the citation graph, not asserted).

Proof

  1. 1
    By L80, , so and (D119). Split on whether .
  2. 2
    Case (so ). A prime's only divisors are and , so (T19, ) divides and is or (D031, D055); would force , excluded. So , and T62 gives , the second claim. Multiplying this congruence by (L74, with by T23): .
  3. 3
    Case . Then is an integer multiple of (L76), so (D113). Multiplying by (L74) and using (L45 (i)): .
  4. 4
    In both cases , and the coprime case additionally gives .
∎

Remarks

Fermat's little theorem (stated 1640). The form holds for every ; the form needs . It is exactly Euler's theorem at a prime modulus, where (L80). It underlies the Fermat primality test and much of public-key cryptography. Examples modulo : and . The converse fails: the Carmichael number satisfies for every yet is composite.
Wikipedia ↗ZMod.pow_card ↗
Propose an edit1 published revision