The strong test asks one question of one base and either proves the number composite or says nothing at all. For 561 — a Carmichael number — 550 of the 558 usable bases prove compositeness and 8 do not; the Fermat test, on the same number, catches none of the 318 coprime bases. The error is one-sided, so t independent bases leave an error of (liars/bases)ᵗ, which is 1024/1690522737399 at t = 5 against a bound of 1/1024.
Core ideas
The hard idea is the asymmetry: one verdict is a proof and the other is silence. The other two are the certificate that makes it a proof and the Carmichael numbers that show why the weaker test is not enough.
If the squaring chain from aᵈ never reaches 1 or n − 1, then n is composite — not probably composite, composite, with a certificate. If it does reach one of them, nothing follows: n may be prime, or a may be one of the bases that happens to be fooled. So repeating the test accumulates evidence in exactly one direction, and a thousand silent bases never add up to a proof of primality.
Modulo a prime, the only solutions of x² = 1 are 1 and −1. So if the chain produces some x that is neither 1 nor n − 1 and whose square is 1, then n cannot be prime, and gcd(x − 1, n) is a proper factor. At n = 341 with a = 2 the chain is 32, 1: 32² = 1024 = 3·341 + 1, so 32 is a nontrivial square root of one and gcd(31, 341) = 31 is a factor. The panel prints that row when it exists.
“At least three quarters of the bases are witnesses” has content only because the other quarter exists. For 561 the strong liars are 50, 101, 103, 256, 305, 458, 460, 511 — eight of 558, so the test clears the bound with enormous room. A single run with base 50 reports nothing, and a reader who stopped there would call 561 prime.
The material
The chain, the certificate, the exact witness fraction, the Carmichael numbers that break the weaker test, and the error after t bases.
Let n be odd and at least 5, and write n − 1 = d·2ˢ with d odd. For a base a in 2..n − 2, compute x₀ = aᵈ mod n and then xᵢ₊₁ = xᵢ² mod n for i up to s − 1. If x₀ = 1 or some xᵢ = n − 1, the base is inconclusive. Otherwise a is a witness and n is composite.
If n is an odd prime, then for every base a in 2..n − 2 the chain reaches 1 at x₀ or reaches n − 1 at some step. Equivalently, a witness exists only for composite n.
Let n be prime. Fermat's little theorem gives aⁿ⁻¹ = a^(d·2ˢ) = 1, so the last term of the chain is 1. Consider the first term of the chain that equals 1.
If it is x₀, the base is inconclusive by the first condition. Otherwise some xᵢ₊₁ = 1 with xᵢ ≠ 1, so xᵢ is a square root of 1 modulo n. Modulo a prime, x² = 1 means n divides (x − 1)(x + 1), so n divides one of the factors and x is 1 or n − 1. Since xᵢ ≠ 1, it is n − 1, and the base is inconclusive by the second condition.
So no base is a witness for a prime, and the contrapositive is the theorem: a witness is a proof of compositeness.
□
The lab confirms the direction that cannot fail by trying every base. At n = 97, all 94 usable bases are inconclusive and the witness count is 0. That is not evidence that 97 is prime — it is a consequence of 97 being prime, and the panel says so, because the test has nothing to offer in that direction.
What the course does not prove is the other half: that at least three quarters of the bases are witnesses for every odd composite. That result is stated here, used in the error arithmetic, and established nowhere in this library. The panel checks it on the n on screen and reports yes or the words that would refute the theorem, which is a test rather than a proof.
For a base a, compute aⁿ⁻¹ mod n. If the result is not 1, then n is composite. If it is 1, the base is inconclusive. The strong test is this test with the squaring chain inspected on the way, and every Fermat witness is a strong witness.
There are composite numbers for which the Fermat test is not merely loose but useless. A Carmichael number satisfies aⁿ⁻¹ = 1 for every a coprime to it, so no coprime base is ever a Fermat witness. The smallest is 561 = 3 · 11 · 17, and Discrete Mathematics names it when it introduces Fermat's little theorem.
The lab splits the Fermat count by coprimality, and the split is not a detail. At n = 561 there are 558 usable bases and 240 of them share a factor with 561; those are caught, because aⁿ⁻¹ cannot be 1 when a and n have a common factor. So the Fermat test catches 240 of 558 bases, which is 40/93, and a panel printing only that fraction would show the Fermat test working about two times in five and would have quietly refuted the Carmichael property. On the 318 coprime bases it catches 0, and that is the number the Carmichael verdict is read off.
558 bases from 2 to 559. The strong test: 550 witnesses, a fraction of 275/279 ≈ 0.9857, against a bound of 3/4. The eight bases that are not witnesses are 50, 101, 103, 256, 305, 458, 460, 511. The Fermat test: 240 witnesses of 558, and 0 of the 318 coprime bases. So the strong test catches 561 with 275/279 of the bases and the Fermat test catches it with none of the bases anyone would have chosen.
Trace base 50, which the panel opens on. 561 − 1 = 560 = 35 · 2⁴, so d = 35 and s = 4. The chain starts at 50³⁵ mod 561 = 560, which is n − 1, so the base is inconclusive at the first step and the squaring never happens. One run with that base reports nothing at all about 561.
Contrast n = 341 = 11 · 31 with a = 2. Here d = 85, s = 2, and 2⁸⁵ mod 341 = 32, which is neither 1 nor 340; squaring gives 1. The chain reached 1 from something other than ±1, so 32 is a nontrivial square root of one and 341 is composite. And 2³⁴⁰ = 1 mod 341, so the Fermat test on the same base says nothing. Same number, same base, one test silent and the other producing a factor.
Because the error is one-sided, t independently chosen bases are wrong about a composite n only if all t are inconclusive. If the fraction of inconclusive bases is q, that has probability qᵗ. The proved bound gives q ≤ 1/4 and so an error of at most 4⁻ᵗ, and the lab prints the exact qᵗ for the n on screen beside 4⁻ᵗ.
At t = 5 on 561 the bound allows about one failure in a thousand and the truth is about one in 1.65 billion. That gap is what “at least three quarters” costs: it has to cover the worst composite, and 561 is nowhere near it. The bound is the guarantee and the exact number is a fact about this n, and only the first survives being applied to a number nobody has enumerated.
The worst of the lab's examples is 2047 = 23 · 89, where 240 of the 2044 bases are inconclusive, a fraction of 60/511 ≈ 0.117. Still well inside 1/4, and the base that fails is 2 — the one everybody tries first. A single-base test with a fixed base is not a randomised algorithm at all; it is a deterministic test with a known counterexample, and someone can look the counterexample up.
Interactive
At least three quarters of the bases are witnesses for a composite — here is the exact fraction, and the smallest base that is not one
Method
Say what each verdict proves before counting anything.
Everything else depends on it, and d must come out odd. At n = 561, 560 = 35·2⁴ so d = 35 and s = 4; at n = 341, 340 = 85·2². The chain has s + 1 entries and the panel labels each one.
Reached 1 at the start, or n − 1 at some step: inconclusive, and nothing follows. Neither: n is composite, proved. Do not soften the second into “probably composite”, and do not harden the first into “probably prime” without the error arithmetic.
If the chain reaches 1 from something other than 1 or n − 1, you have a factor: gcd(x − 1, n). The panel prints that row when it appears, and it is the difference between a verdict and a certificate.
A fixed base is a published counterexample waiting to be used — base 2 fails on 2047. t random bases leave an error of at most 4⁻ᵗ, and the panel shows the exact figure for this n alongside, usually many orders of magnitude smaller.
561 with base 50, and 341 with base 2. The first produces no testimony and the second produces a factor, and the arithmetic in both is a squaring chain.
The 341 trace is the argument for the strong test in four lines. The Fermat test computes 2³⁴⁰ and looks only at the answer, which is 1, and learns nothing. The strong test computes the same power by the same squaring chain and looks at the intermediate values, one of which is a nontrivial square root of one. Same work, more information, because it did not throw the chain away.
Base 50 on 561 is the other half. It is one of only eight bases out of 558 that fail, and it is the base the panel opens on, deliberately: a lesson whose lab opens on a base that works would be showing the test succeeding and calling that an illustration of a probabilistic guarantee.
For a faded rehearsal, set n = 1105 and predict the two Fermat columns before reading them. The supplied first move is this: 1105 is 5 · 13 · 17 and it is a Carmichael number, so the coprime column is 0. Work out how many of the 1102 bases are coprime to 1105, say what the other Fermat column must therefore be, and then check both — and then say how many strong liars you expect and compare.
You should be able to factor n − 1 as d·2ˢ, run the chain, recognise a nontrivial square root of one and extract a factor from it, explain why no base witnesses a prime, split a Fermat count by coprimality, and compute the exact error after t random bases.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.