Fermats little theorem — the series

1. 

   Necklaces that prove a theorem

   Thread five beads in two colours, thirty-two ways. Two of them are all one colour; the other thirty fall into rings of five. That count, and nothing else, is Fermat's little theorem.

   part 1 · number
2. 

   One residue whose powers are all of them

   Fermat's theorem says every order divides p − 1. It does not say that anything has order exactly p − 1, which is a separate and stronger claim — and what forces it is a count of how many numbers share each divisor with p − 1.

   part 2 · number
3. 

   The exponent that is smaller than Euler's

   Euler's theorem raises every unit to the count of the units and gets one. The smallest exponent that works for all of them at once is often much smaller — and a composite is invisible to Fermat's test exactly when that smaller number divides n − 1.

   part 3 · number
4. 

   An order that proves a prime

   Fermat's little theorem is a test that primes pass and composites mostly fail, and it can be fooled. Run backwards, it cannot. If some number a has order exactly n − 1 modulo n, then n is prime — because only a prime has n − 1 numbers to cycle through. Checking that takes the prime factors of n − 1, which need proofs of their own, and the proofs nest into a tree that anyone can check: Pratt's certificate, which shows every prime has a short proof of being one.

   part 4 · number
5. 

   Two primes where Fermat holds twice

   Fermat's theorem says p divides 2^(p−1) − 1. Usually p² does not. It does at 1093 and at 3511 and at no other prime anyone has found, in searches reaching past 10^19. The leftover, (2^(p−1) − 1)/p taken mod p, behaves like a random number, so a prime has about a one-in-p chance of the extra divisibility — and a random count with that chance grows so slowly that two by now is unremarkable, while nobody can prove there are any more, or that there are infinitely many primes where it fails.

   part 5 · number
6. 

   The row that proves a prime

   Fermat's little theorem can be fooled: 561 passes it for every base and is not prime. Thread necklaces with a fixed number of black beads instead of any colours at all, and the count becomes a statement about a whole row of Pascal's triangle — every middle entry of row n is a multiple of n exactly when n is prime — which no composite can fake. Written as polynomials it is (x + a)ⁿ = xⁿ + a, and cut down to size it is the first proof that primes can be recognised in polynomial time.

   part 6 · number
7. 

   How often two generates every remainder

   For some primes p, the powers of 2 run through every non-zero remainder before repeating; for others they get stuck in a smaller cycle. Among the primes up to two million the first kind make up 37.43% — and Artin predicted 37.40% in 1927 by treating each way of getting stuck as an independent accident. For the base 5 the same prediction is wrong, because two of the accidents are secretly the same one, and nobody can yet prove that 2 works for infinitely many primes at all.

   part 7 · number
8. 

   The numbers that fool every base

   561 = 3 · 11 · 17 passes Fermat's test for every base it shares no factor with, and so do 1,105, 1,729 and 102 more numbers below ten million. They were proved infinite only in 1994. Counted to 10²¹ there are about twenty million, growing like x to a power that has crept from 0.21 to 0.35 — just past the bound the proofs guarantee and nowhere near the power of one that Erdős's argument predicts.

   part 8 · number
9. 

   A quarter of the bases at most

   Carmichael numbers pass Fermat's test for every base they share no factor with, so Fermat's test can be fooled for ever. Watch the squarings on the way to aⁿ⁻¹ instead, and a prime allows only one pattern; 561 lets just 10 of its 320 bases through, and Monier and Rabin proved that no odd composite but 9 lets through more than a quarter. Four fixed bases prove every number below 3.2 billion prime or not.

   part 9 · number

All series