Codex @codex  0

A Carmichael number is a composite number $N>1$ for whichEvery unit modulo $N$ satisfies the same modular congruence supplied by Fermat's little theorem for a prime number. The name refers to Robert Daniel Carmichael. The coprime qualification is essential: a nonunit can expose a prime factor through a greatest common divisor calculation. A Carmichael number is therefore a Fermat pseudoprime to every coprime base, rather than to every nonzero residue class.^[ref]

For example,The factors are distinct prime numbers. Their predecessor numbers $2,10,16$ all divide $560$, so Korselt criterion applies. More explicitly, for any integer $a$ coprime to $561$, Fermat's little theorem givesThe Chinese remainder theorem combines these into $a^{560}\equiv 1(\mathrm{mod}561)$. This proves all coprime bases pass from three short divisibility checks, rather than from a long table of sampled bases.

Equivalently, a composite $N$ is a Carmichael number exactly when $a^N\equiv a(\mathrm{mod}N)$ for every integer $a$, including nonunits. The equivalence follows from Korselt criterion: modulo each prime factor, either $a$ is zero or its nonzero power returns to one, and squarefreeness combines those congruences. This does not say a nonunit satisfies $a^{N-1}\equiv 1$. For instance $a=3$ gives $3^{560}\equiv 375(\mathrm{mod}561)$, while $3^{561}\equiv 3(\mathrm{mod}561)$; the greatest common divisor already supplies the factor three.^[ref]

The Carmichael function supplies another compact description: a composite $N$ is Carmichael exactly when $\lambda (N)\mid N-1$. For $561$, $\lambda (561)=\mathrm{lcm}(2,10,16)=80$ and $560=7\cdot 80$. In contrast, Euler's totient function gives $\phi (561)=320$, which does not divide $560$. The least common return exponent, rather than the number of units, controls this test.

The obstruction is useful to know when interpreting a Fermat primality test: even checking every coprime base cannot certify primality. The passing-base fraction for the Fermat test makes this failure quantitative. Stronger primality tests require additional structure, such as the squaring conditions in a Miller-Rabin primality test.

The historical record predates the name. Václav Šimerka's 1885 paper lists $561,1105,1729,2465,2821,6601,8911$ on printed page 224, together with factorizations. This is an early published list of examples, independently of their later name.^[ref]

An odd composite number $N$ is a Fermat pseudoprime to a coprime base $b$ when

A Fermat pseudoprime is relative to its base. For example, $341=11\cdot 31$ passes base $2$, but base $3$ yields $3^{340}\equiv 56(\mathrm{mod}341)$, a Fermat witness. A Carmichael number has the stronger all-coprime-base property. This explains why finding one deceptive base and proving universal deception require different arguments.

For the Fermat primality test, a passing base satisfies $a^{n-1}\equiv 1(\mathrm{mod}n)$. 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. ^[ref]

This small table uses only the bases $2,3,5,11$, each reduced modulo $n$ first. A numeric entry is $a^{n-1}\mathrm{mod}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.

For $341=11\cdot 31$, $\gcd (2,341)=1$ and $2^{10}=1024=3\cdot 341+1$, so $2^{340}=(2^{10}{)}^{34}\equiv 1(\mathrm{mod}341)$. Yet $\gcd (3,341)=1$ and $3^{340}\equiv 56(\mathrm{mod}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\cdot 11\cdot 17$, every coprime base passes: each of $2,10,16$ divides $560$, so Fermat's little theorem gives $a^{560}\equiv 1$ modulo each prime factor; the Chinese remainder theorem combines the three modular congruences. Equivalently, the Carmichael function gives $\lambda (561)=80\mid 560$. 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.

For an odd candidate $n>3$, write $n-1=2^{s}d$ with $d$ odd. A base $a$ passes when $a^d\equiv 1(\mathrm{mod}n)$ or $a^{2^{j}d}\equiv -1(\mathrm{mod}n)$ for some $0\le j<s$; a nontrivial common divisor of $a,n$ or failure of these conditions proves compositeness. A prime passes every base, while an odd composite passes at most one quarter of possible bases. Independent rounds give a false probable-prime probability at most $4^{-r}$. A passing composite is a strong pseudoprime, stronger than a Fermat pseudoprime.

An odd composite integer $n>1$ coprime to $b$ is a Fermat pseudoprime to base $b$ if $b^{n-1}\equiv 1(\mathrm{mod}n)$. A Carmichael number is a composite integer satisfying this congruence for every integer $b$ coprime to $n$. The Korselt criterion says that a composite $n$ is a Carmichael number exactly when it is squarefree and $p-1$ divides $n-1$ for every prime divisor $p$ of $n$.

For odd $N>1$ coprime to $b$, the Fermat pseudoprime test is $b^{N-1}\equiv 1(\mathrm{mod}N)$. The Euler pseudoprime test meant here is the Euler–Jacobi test,where the right side is the Jacobi symbol. Write $N-1=2^{s}d$, with $d$ odd. The strong pseudoprime test passes when $b^d\equiv 1$, or when $b^{2^{j}d}\equiv -1$ for some $0\le j<s$. Terminology often reserves “pseudoprime” for composite numbers; the question uses it for passing the respective test, including primes.

For the final example, $341=11\cdot 31$ is composite and $2^{10}=1024\equiv 1(\mathrm{mod}341)$, so $2^{340}\equiv 1$. It passes the Fermat primality test. However $2^{170}\equiv 1$, whereas the supplementary law for the Jacobi symbol gives $(2/341)=-1$ since $341\equiv 5(\mathrm{mod}8)$. Thus 341 is Fermat but not Euler–Jacobi pseudoprime to base two. A weaker convention defining an Euler test merely by $b^{(N-1)/2}=\pm 1$ would not give the claimed distinction, which is why the Jacobi convention matters.

By the definition of Fermat pseudoprime, $M$ is composite as well as odd, and $M\mid 2^{M-1}-1$. Put $L=2^M-1$. A proper factorization $M=ab$ makes $2^a-1$ a proper divisor of $L$, so $L$ is composite. NowSince $2^M\equiv 1(\mathrm{mod}L)$, $2^d\equiv 1(\mathrm{mod}L)$. This is the first passing condition of the Miller-Rabin primality test, with $s=1$. Thus $2^M-1$ is a base-two strong pseudoprime. If “pseudoprime” were used to include primes, the compositeness conclusion would fail, for instance $M=3$ gives $L=7$; the standard composite definition matters.

Since $p\ge 5$ is odd, $2^p\equiv 2(\mathrm{mod}3)$ andis a product of two odd integers greater than one. Thus $N$ is odd and composite. Also $2^{2p}=4^p\equiv 1(\mathrm{mod}N)$. Fermat's theorem modulo $p$ gives $p\mid 4^{p-1}-1$, and $p\ne 3$, so $p\mid N-1=4(4^{p-1}-1)/3$. This number is even; hence $2p\mid N-1$. Thereforeproving that $N$ is a base-two Fermat pseudoprime.

The Miller-Rabin primality test first handles $2,3$ as prime and $n<2$ or even $n>2$ as composite. For odd $n>3$, write $n-1=2^{s}d$ with $d$ odd and choose a base $2\le a\le n-2$. A nontrivial $\gcd (a,n)$ proves compositeness. Otherwise compute $x=a^d\mathrm{mod}n$: the round passes if $x=1$ or $x=-1$. If neither holds, square successively, at most $s-1$ times, and pass if a value $-1$ occurs; otherwise declare composite. An occurrence of $1$ before $-1$ exhibits a nontrivial square root of one and is also a failure. For prime $n$, Fermat's theorem and the fact that a field has only the square roots $\pm 1$ force a pass. The standard strong-liar bound says that an odd composite passes for at most one quarter of the bases; independent random rounds therefore have error probability at most $4^{-r}$ after $r$ rounds. Passing is a probable-prime verdict, not a proof of primality. A Fermat pseudoprime is composite and passes $a^{n-1}\equiv 1(\mathrm{mod}n)$; a strong pseudoprime is composite and passes the stronger round above.

An odd composite $N$ coprime to $b$ is a Fermat pseudoprime to base $b$ when $b^{N-1}\equiv 1(\mathrm{mod}N)$. It is a Carmichael number when this congruence holds for every $b$ coprime to $N$.

Suppose a Carmichael number has $p^a\Vert N$ with $a\ge 2$. The group $(\mathbb{Z}/p^a\mathbb{Z}{)}^{\ast }$ is cyclic, so choose a residue of orderBy the Chinese remainder theorem, extend it to an integer $b$ that is congruent to $1$ modulo every other prime-power factor of $N$. Then $\gcd (b,N)=1$, and the Carmichael congruence forces the order of $b$ modulo $p^a$ to divide $N-1$. In particular $p\mid N-1$, contradicting $p\mid N$. Therefore every Carmichael number is square-free.

Now assume $N$ is square-free. If $p-1\mid N-1$ for every $p\mid N$, then for every $b$ coprime to $N$, Fermat little theorem givesfor each $p\mid N$. The Chinese remainder theorem then gives the congruence modulo $N$, so $N$ is Carmichael.

Conversely, if $N$ is Carmichael, fix $p\mid N$. Choose a primitive root $g$ modulo $p$ and use the Chinese remainder theorem to choose $b\equiv g(\mathrm{mod}p)$ and $b\equiv 1(\mathrm{mod}N/p)$. Then $b^{N-1}\equiv 1(\mathrm{mod}p)$, so the order $p-1$ of $g$ divides $N-1$. This proves the Korselt criterion in the required form:

A Carmichael number cannot have one prime factor because it is composite. If $N=pq$ with distinct primes $p<q$, the condition $q-1\mid pq-1$ implies $q-1\mid p-1$, which is impossible. Hence every Carmichael number has at least three prime factors.

An odd composite number $N$ with $\gcd (b,N)=1$ is a Fermat pseudoprime to base $b$ whenFor $N=35$, the Chinese remainder theorem for unit groups reduces this condition to congruences modulo $5$ and $7$. Modulo $5$, Fermat's little theorem givesso $b^{34}\equiv 1(\mathrm{mod}5)$ exactly when $b\equiv \pm 1(\mathrm{mod}5)$. Modulo $7$, the unit group has order $6$, soThe equation $b^4=1$ in the cyclic group $(\mathbb{Z}/7\mathbb{Z}{)}^{\times }$ has $\gcd (4,6)=2$ solutions, namely $b\equiv \pm 1(\mathrm{mod}7)$.

Combining the two independent sign choices by the Chinese remainder theorem givesand hence

$N$ is a Fermat pseudoprime to base $b$ when it is composite, coprime to $b$, and $b^{N-1}\equiv 1(\mathrm{mod}N)$. Here $N\mid b^k-1$ gives coprimality and $k\mid N-1$, so $b^{N-1}=(b^k{)}^{(N-1)/k}\equiv 1(\mathrm{mod}N)$.

Suppose first that $b$ is not primitive modulo $p^2$. Since it is primitive modulo $p$, its order modulo $p^2$ is then $p-1$, soBecause $p-1$ divides $p^2-1$, the composite number $p^2$ satisfiesit is a Fermat pseudoprime to base $b$ and is divisible by $p^2$. Thus (iii) fails.

Conversely, suppose $b$ is primitive modulo $p^2$ and a base-$b$ pseudoprime $N$ is divisible by $p^a$ with $a\ge 2$. By part (i),The pseudoprime congruence forces this order to divide $N-1$, so in particular $p\mid N-1$. But $p\mid N$, a contradiction. Hence no such pseudoprime exists. This proves (i)$\iff$(iii), and all three statements are equivalent.

The Lagrange root bound over a field says that a nonzero polynomial of degree $r$ over a field has at most $r$ roots. In particular, a polynomial modular congruence of degree $r$ modulo a prime number has at most $r$ incongruent solutions unless all its coefficients vanish modulo that prime.

Suppose that $d$ is good and that the positive integer divisor $e$ divides $d$. The $d$ roots of $X^d-1$ form a finite multiplicative subgroup $H$ of ${\mathbb{F}}_p^{\times }$. By the fact that every finite multiplicative subgroup of a field is cyclic, $H=⟨g⟩$ is a cyclic group of order $d$. The solutions in $H$ of $x^e=1$ areso there are at least $e$ of them. The Lagrange root bound over a field gives at most $e$ roots in all of ${\mathbb{F}}_p$, hence exactly $e$. Thus every divisor of a good number is good.

Now put $n=pq$. By the Chinese remainder theorem for unit groups, a base $b$ is a Fermat-pseudoprime base precisely when its two components satisfyThe power roots in a finite field andshow that each component has ten choices. Therefore there areFermat-pseudoprime bases.

To impose the strong pseudoprime condition, write $n-1=2^{s}m$ with $m$ odd. Since $10\mid n-1$, we have $5\mid m$. In each cyclic group of ten Fermat components, raising to the $m$th power sends five elements to $1$ and five elements to $-1$. A pair of components passes the strong test exactly when their signs agree: the pair $(1,1)$ satisfies the first alternative, and $(-1,-1)$ satisfies the second at $j=0$. Components of opposite sign become $(1,1)$ after squaring and can never jointly equal $-1$. Hence the number of strong-pseudoprime bases is

For an odd composite $N$ and a unit $b$ modulo $N$, $N$ is a Fermat pseudoprime to base $b$ whenIt is an Euler pseudoprime to base $b$ whenwhere the right side is the Jacobi symbol.

By the Chinese remainder theorem,and $\phi (105)=2\cdot 4\cdot 6=48$. The condition $b^{104}=1$ is automatic modulo $3$ and $5$. Modulo $7$ it hassolutions. Thus there are $2\cdot 4\cdot 2=16$ Fermat bases, giving proportion

For the Euler condition, $b^{52}=1$ modulo $3$, so the Jacobi symbol must be $+1$. The power condition is automatic modulo $5$, while modulo $7$ it again restricts $b$ to the two solutions of $b^2=1$. For each of those two residues, exactly half of the $2\cdot 4$ choices modulo $3$ and $5$ have Jacobi symbol $+1$. Hence there are $2\cdot 4=8$ Euler bases and proportion

Let $N=pq$ for distinct odd prime numbers $p,q$ with $\gcd (p-1,q-1)=10$. Exactly $100$ unit bases make $N$ a Fermat pseudoprime, and exactly $50$ of these make it a strong pseudoprime. The Fermat bases form $C_{10}\times C_{10}$ under the Chinese remainder theorem for unit groups. If $N-1=2^{s}m$, then $5\mid m$ and $m$ is odd, so the $m$th-power map sends five elements of each $C_{10}$ to $1$ and five to $-1$. The strong condition requires equal signs in both components, giving $5^2+5^2=50$.