Concept

Order of an element

The smallest number of times an element must be combined with itself to give the identity. It divides the size of the group — Lagrange's theorem — and knowing an element's order exactly is how one certifies that a group is as large as it is claimed to be.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

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.

number · Fermats little theorem

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.

number · Fermats little theorem

Named alongside it

The objects these essays reach for when they reach for this one.

Fermats little theorem Prime Carmichael number Fermat last theorem Heuristic Modular arithmetic Primality test Primitive root

All concepts