= Fermat test example
{c}
For the <Fermat primality test>, a passing base satisfies $a^{n-1}\equiv1\pmod n$. \b[Passing proves only this <modular congruence>, not that $n$ is a <prime number>.] An odd <composite number> that passes a <coprime> base is a <Fermat pseudoprime> to that base. A <Carmichael number> passes every <coprime> base, so even testing all the <units> would not certify that $n$ is a <prime number>. <Fermat's Test by Keith Conrad>[Keith Conrad, Fermat's Test, pp. 5–6, Definition 4.1 and the list beginning with 561]{ref}
This small table uses only the bases $2,3,5,11$, each reduced modulo $n$ first. A numeric entry is $a^{n-1}\bmod n$: one passes, while any other numeric entry gives a <Fermat witness>. A "factor" entry records a proper <greatest common divisor> and stops before <modular exponentiation>. The prime/composite classification is independently established by <trial division> or the displayed <prime factorization>, not by the passing entries. These four bases are illustrative, with no asserted universal coverage or error probability.
\Table[
|| $n$
|| Independent classification
|| $a=2$
|| $a=3$
|| $a=5$
|| $a=11$
| 2
| <Prime number>
| Zero residue: excluded
| 1
| 1
| 1
| 7
| <Prime number>
| 1
| 1
| 1
| 1
| 15
| $3\cdot5$: <composite number>
| 4
| Factor 3
| Factor 5
| 1
| 341
| $11\cdot31$: <composite number>
| 1
| 56
| 67
| Factor 11
| 561
| $3\cdot11\cdot17$: <composite number>
| 1
| Factor 3
| 1
| Factor 11
]
{title=Finite-base <Fermat primality test> examples with explicit <greatest common divisor> checks}
For $341=11\cdot31$, $\gcd(2,341)=1$ and $2^{10}=1024=3\cdot341+1$, so $2^{340}=(2^{10})^{34}\equiv1\pmod{341}$. Yet $\gcd(3,341)=1$ and $3^{340}\equiv56\pmod{341}$, so three is a <Fermat witness>. One <coprime> base passes and another fails: being a <Fermat pseudoprime> depends on the base. Choosing eleven instead reveals the proper factor through $\gcd(11,341)=11$.
For $561=3\cdot11\cdot17$, every <coprime> base passes: each of $2,10,16$ divides $560$, so <Fermat's little theorem> gives $a^{560}\equiv1$ modulo each <prime factor>; the <Chinese remainder theorem> combines the three <modular congruences>. Equivalently, the <Carmichael function> gives $\lambda(561)=80\mid560$. Bases two and five have <greatest common divisor> one and pass, but $\gcd(3,561)=3$, $\gcd(11,561)=11$ and $\gcd(17,561)=17$ expose factors. The qualification "<coprime>" is therefore crucial even for a <Carmichael number>.
The <Fermat primality test> is useful because a <Fermat witness> can prove compositeness using <repeated squaring> without finding a factor. Its failure to certify a passing candidate motivates stronger <primality testing> methods such as the <Miller-Rabin primality test>.
Back to article page
