Concept

Carmichael number

A composite number n for which a to the power n − 1 leaves remainder one modulo n for every a sharing no factor with n. It passes Fermat's primality test for every base, and Korselt's criterion says it is squarefree with p − 1 dividing n − 1 for each prime p dividing it.

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 first ten Carmichael numbers and the divisions that make them. 561 = 3·11·17; 1105 = 5·13·17; 1729 = 7·13·19; 2465 = 5·17·29; 2821 = 7·13·31; 6601 = 7·23·41; 8911 = 7·19·67; 10585 = 5·29·73; 15841 = 7·31·73; 29341 = 13·37·61.

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.

number · Fermats little theorem

Named alongside it

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

Exhaustive search Fermats little theorem Heuristic Open problem Order of an element Primality test Prime Primes Primitive root Pseudoprime

All concepts