THE FERMAT PRIMALITY TEST if a^(p-1) is not 1, p is not prime; if it is, maybe
Fermat’s little theorem says that for a prime p and any base a not divisible by it, a^(p-1) ≡ 1 (mod p). So compute a^(n-1) mod n: if it is not 1, n is certainly composite. If it is 1, n is probably prime — the first, fast, one-sided primality test, and the direct ancestor of Miller-Rabin.
THE TECHNIQUE a^(n-1) mod n by fast exponentiation
Test a number with base 2. A prime always passes. But some composites lie: 341 = 11×31 gives 2^340 ≡ 1 (mod 341) — a Fermat pseudoprime. Try primes and liars and watch the test pass on both: live demo
HISTORY & CREDIT Fermat 1640; proof Euler 1736
“Passing the Fermat test proves primality.” — no. It is one-sided: failing proves compositeness, but passing does not prove primality — pseudoprimes pass, and Carmichael numbers (dart 184) pass for every base. It certifies “composite” with certainty and “prime” only with suspicion. cited
1640 · Pierre de Fermat — states the little theorem in a letter to Frénicle de Bessy (no proof, as was his habit). 1736 · Leonhard Euler — the first published proof; later generalises it to a^φ(n) ≡ 1 (Euler’s theorem). 1819 · Sarrus — finds the first pseudoprime, 341, showing the converse fails; the crack that Miller-Rabin (dart 032) later seals.
The fast-exponentiation that makes it practical — square-and-multiply, O(log n) multiplications — is the same engine under RSA (dart 050) and Diffie-Hellman (035); the primality test and the cipher share one modular-power routine. Fermat 1640 / Euler 1736
RECOMMEND FOR I-13 the test, and its lie, computed
On the canonical compiler the test passes for a prime and is fooled by the pseudoprime 341 — modular power by bitwise square-and-multiply:
$ i13 run fermat.i13 # a^(n-1) mod n, exponent halved by >> (bitwise)
2^16 mod 17 = 1 -- 17 prime: passes (true)
2^340 mod 341 = 1 -- 341 = 11x31 COMPOSITE: passes anyway (a Fermat pseudoprime)
Recommend: the Fermat test is LIT on I-13 — verified 2^16 ≡ 1 (mod 17) (a true prime) and the pseudoprime 2^340 ≡ 1 (mod 341) (a composite that lies), by a modexp that halves the exponent with >> and tests the low bit with & (the bitwise operators darts 001/029 asked for — and ⚠ float division / would silently break it: 85/2 = 42.5, so the exponent must be shifted, not divided). It is the seed of the whole probabilistic-primality line already in the corpus (Rabin-Miller 032, RSA 050); its one honest weakness — Carmichael numbers — is the next dart.