Matpic
mathematics, in pictures
Series

Fermats little theorem — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Necklaces of 5 beads in 2 colours. Every string of beads, grouped by the rotations that carry one onto another.

    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. The powers of 2 modulo 13, as a ring of 12. The non-zero residues modulo 13 placed on a circle, with the successive powers of 2 joined by straight lines into a closed walk of 12 steps.

    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 orders of the 8 units modulo 15. A strip of the units modulo 15 with each one's multiplicative order beneath it, the largest order marked at 4 against φ(15) = 8.

    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. A witness that 97 is prime: 5 has order 96. A table of the checks Lucas's test makes on 97 with base 5: the power (n − 1)/q for each prime q dividing n − 1, none of which is 1.

    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. The Fermat quotient of 2 at every prime up to 4000, and where it is 0. A scatter of the Fermat quotient of 2 modulo p, divided by p, against p for the primes up to 4000; the points spread evenly between zero and one and reach zero at the Wieferich primes.

    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

All series