Call a witness
Pick a candidate number n and a base a smaller than
it. The base is asked whether the candidate behaves like a prime under modular
exponentiation.
Witness numbers / Miller-Rabin
1662803
1,662,803 is a prime number with one unusually specific job: it is the largest
base in the four-base Miller-Rabin test 2, 13, 23, 1662803, which
determines primality for every integer below 1,122,004,669,633.
It is prime
The Prime Curios page for 1662803 identifies the number as prime.
Jaeschke's four-base set
Prime Curios attributes the four-base result to Gerhard Jaeschke.
Deterministic below 1.122 trillion
Wikipedia gives the exact upper bound used here.
The witness story
How the idea is introduced
Numberphile's "Witness Numbers" explains the test in three moves: call a witness, discover that some witnesses can lie, then switch to carefully chosen witnesses that give deterministic results over practical ranges.
Meet a strong liar
A composite number can pass the Miller-Rabin check for some bases. The video uses 91 with base 10 to show how a base can approve a composite candidate.
Use known witnesses
The story then shifts from random bases to curated base sets. This is where
1662803 appears as the final member of a compact four-base test.
The test in one page
How Miller-Rabin reads a candidate
For an odd candidate n > 2, write n - 1 as
2^s * d, where d is odd. A base a
passes when the modular powers land on 1 or on -1
at the right stage.
A failed base proves the candidate is composite. A passed base gives evidence, and carefully chosen base sets give certainty within documented ranges.
01
Reduce the candidate:
n - 1 = 2^s * d.
02
Compute
a^d mod n and then square through the powers of two.
03
One revealing base is enough to prove compositeness.
Worked examples
The two teaching cases
These two examples show both sides of the test: one base exposes a composite number, and another base gets fooled by a composite number.
747 with base 23
The candidate is 747. Its reduced form is
747 - 1 = 2 * 373, so the first check uses exponent
373.
23^373 mod 747 = 131
131 is neither 1 nor -1 mod 747
Base 23 reveals that 747 is composite. The verdict is mathematically final after one failed witness.
91 with base 10
The candidate is 91, and 91 - 1 = 2 * 45. The
video uses base 10 to show a passing base for a composite
number.
10^45 mod 91 = 90
90 == -1 mod 91
The base passes, although 91 = 7 * 13. This is the strong-liar
phenomenon that makes random testing probabilistic.
Why 1662803 matters
The compact deterministic set
Prime Curios gives the high-level statement: Jaeschke showed that four bases determine primality for integers with twelve or fewer digits, with 1662803 as the largest base. Wikipedia gives the exact upper bound used here.
2first base in the set
13second base
23third base
1662803largest and most distinctive base
| Base set | Guaranteed range | Why it is included |
|---|---|---|
2, 3 |
n < 1,373,653 |
Smallest example from the video and Wikipedia's deterministic table. |
2, 3, 5 |
n < 25,326,001 |
Shows how one more base expands the range. |
2, 13, 23, 1662803 |
n < 1,122,004,669,633 |
The compact four-base result that makes 1662803 notable. |
2, 3, 5, 7, 11 |
n < 2,152,302,898,747 |
A five-prime alternative discussed in the Numberphile episode. |
Reading the number correctly
Three precise claims
It is prime
The Prime Curios page identifies 1662803 as a prime number.
It helps test other numbers
In Miller-Rabin, 1662803 is a base a. The candidate
being tested is another integer n in the documented range.
It is memorable because it is odd-looking
The first three bases are small. The jump to 1662803 is what
gives the Numberphile episode its hook.
Sources
References
These references cover the curiosity entry for 1662803, the Miller-Rabin algorithm and its deterministic variants, and the witness-story presentation.