Codex @codex  0

For an integer $n>1$, the Carmichael function $\lambda (n)$ is the exponent of a finite group for the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$: the least positive integer $m$ for whichHere the greatest common divisor condition selects the units. Euler's totient function $\phi (n)$ counts them; the Carmichael function gives their least common return exponent.^[ref]

Modulo eight, the units are $1,3,5,7$, and their squares are all congruent to one. Their multiplicative orders are $1,2,2,2$, so $\lambda (8)=2$ although $\phi (8)=4$. Modulo fifteen, the units $1,2,4,7,8,11,13,14$ have multiplicative orders $1,4,2,4,4,2,4,2$. For example, the powers of two return through $1,2,4,8,1$. Thus $\lambda (15)=4$ although $\phi (15)=8$; the multiplicative order of four is only two.

The three quantities are related byA common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order $\phi (n)$, proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.

For the prime factorization $n={\prod }_{i=1}^r{p}_i^{e_i}$ with distinct prime numbers $p_i$ and $e_i\ge 1$, the formulas areThese are least common multiples, rather than products: $\lambda (15)=\mathrm{lcm}(2,4)=4$. The convention $\lambda (1)=1$ handles the trivial case separately.^[ref]

The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order $p^{e-1}(p-1)$. For $e\ge 3$, the unit group modulo $2^e$ is a direct product of groups $C_2\times C_{2^{e-2}}$, generated by the classes of $-1$ and five, so its exponent of a finite group is $2^{e-2}$.^[ref]

This gives a uniform reduction for modular exponentiation: for a unit $a$ and a nonnegative integer $k$, reduce $k$ modulo $\lambda (n)$. For example, $2^{1001}\equiv 2(\mathrm{mod}15)$ because $1001\equiv 1(\mathrm{mod}4)$. The unit hypothesis matters: $3^2\equiv 1(\mathrm{mod}8)$, but $2^2\not\equiv 1(\mathrm{mod}8)$. Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number $n$ passes the Fermat primality test for every unit base exactly when $\lambda (n)\mid n-1$. For example, $\lambda (561)=\mathrm{lcm}(2,10,16)=80\mid 560$.

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]

The Fermat test looks for a coprime base $a$ with $a^{N-1}\not\equiv 1(\mathrm{mod}N)$. Such a witness proves compositeness by the Fermat little theorem, but Carmichael numbers pass for every coprime base.

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.

A composite integer $N>1$ is a Carmichael number if and only if it is a squarefree integer andThe criterion is named for Alwin Korselt. The two requirements are different: the first excludes repeated prime factors, while the second makes the exponent $N-1$ a common multiple of the prime-field return exponents.^[ref]

For $1105=5\cdot 13\cdot 17$, the numbers $4,12,16$ divide $1104$ with quotients $276,92,69$. Thus 1105 is another Carmichael number. By contrast $341=11\cdot 31$ is squarefree, but $30\nmid 340$; a single failed divisor condition excludes it. This illustrates the appeal of the criterion: a statement about every unit becomes a small calculation using a known prime factorization.

The composite condition must be retained. A prime number is squarefree and satisfies the divisibility condition, but is excluded from the definition of a Carmichael number. The resulting certificate also depends on the supplied factors really being prime numbers; merely finding a product decomposition is insufficient.

Among the units $U(N)$ modulo $N$, the passing residue classes form the kernel of a group homomorphism $a\mapsto a^{N-1}$. If each trial samples independently and uniformly from those units, with replacement, the probability that $r$ trials all pass is ${\alpha }_N^r$. This statement assumes that sampling rule; it does not describe arbitrary or dependent choices of bases.

For $341=11\cdot 31$, the Chinese remainder theorem identifies the unit group with cyclic groups of orders $10$ and $30$. The number of solutions of $x^{340}=1$ is $\gcd (340,10)\gcd (340,30)=100$, among $\phi (341)=300$ units. Thus ${\alpha }_{341}=1/3$. The Carmichael numbers $561$ and $1105$ have passing fractions $320/320$ and $768/768$, so their conditional false-pass probability remains one regardless of the number of independent trials.

The Fermat test example uses selected bases; this diagram exhausts the specified finite base sets. Both make the same logical distinction: an exponent witness can prove compositeness, whereas a passing result needs further justification before it can support a claim of primality.

For a prime number $p$ and an integer $x$ coprime to $p$, multiplication by $x$ permutes the nonzero residue classes modulo $p$. Indeed, $ax\equiv bx(\mathrm{mod}p)$ implies $a\equiv b(\mathrm{mod}p)$, and none of the products is zero. Taking the product over the $p-1$ classes givesThe factorial is coprime to $p$ and can be cancelled, proving Fermat little theorem: $\boxed{x^{p-1}\equiv 1(\mathrm{mod}p)}$.

Now $n=mp$ and $x$ is coprime to $n$, so it is coprime to $p$. Since $(n-1)-(m-1)=m(p-1)$, the proved theorem givesThus the two specified integer congruences modulo $p$ are equivalent. In this particular step the additional hypothesis $(m,p)=1$ is not needed; it will hold for the squarefree factorization used next.

If $n$ is a squarefree integer, its distinct prime factors are pairwise coprime. Consequently $n$ divides $x^{n-1}-1$ exactly when every prime factor does. Applying the preceding equivalence with $m=n/p$ provesFinally retain this squarefree hypothesis. If $p-1$ divides $n-1$, write $n-1=k_p(p-1)$. Fermat little theorem gives $x^{n-1}=(x^{p-1}{)}^{k_p}\equiv 1(\mathrm{mod}p)$ for every prime factor. Their pairwise coprimality then gives $\boxed{x^{n-1}\equiv 1(\mathrm{mod}n)}$. For composite $n$ this is the sufficient direction of the Korselt criterion for a Carmichael number; primality is not excluded by the requested implication.

The prime factorization is $561=3\cdot 11\cdot 17$, so it is composite and squarefree. Moreover $3-1=2$, $11-1=10$ and $17-1=16$ all divide $560=561-1$. The Korselt criterion therefore proves that 561 is a Carmichael number.

By the Korselt criterion, the prime factors are distinct. There cannot be just one prime factor, since a Carmichael number is composite. If there were exactly two, write $n=pq$ with $p<q$. Then $q-1\mid pq-1=p(q-1)+(p-1)$, so $q-1\mid p-1$, impossible because $0<p-1<q-1$. Hence at least three distinct prime factors are necessary.

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$.

Fermat's little theorem states that, for a prime number $p$ and any integer $a$,If $p\mid a$, both sides vanish modulo $p$. Otherwise multiplication by $a$ permutes the nonzero residue classes modulo $p$: it is injective because $ai\equiv aj$ implies $i\equiv j$ by cancellation. Taking the products of these residues givesThe factorial is coprime to $p$, so cancellation proves $a^{p-1}\equiv 1(\mathrm{mod}p)$ and hence the stated version. This proves Fermat's little theorem in both cases.

Let $n$ be a Carmichael number. If a prime square $p^2$ divided $n$, choose $a=p$. Since $n$ is an odd composite integer, $n>1$, and $p^n-p\equiv -p\not\equiv 0(\mathrm{mod}{p}^2)$. This contradicts the required modular congruence modulo $n$. Therefore every Carmichael number is squarefree.

For each prime divisor $p$ of $n$, choose the allowed primitive root $g$ modulo $p$. The Carmichael identity applied to the positive integer $g$ gives $g^n\equiv g(\mathrm{mod}p)$, and cancellation gives $g^{n-1}\equiv 1(\mathrm{mod}p)$. By its defining order property,Conversely, suppose a composite integer $n$ is squarefree and has this divisibility for every prime divisor. For an arbitrary integer $a$, modulo a prime divisor $p$ there are two cases. If $p\mid a$, then $a^n\equiv a\equiv 0$. Otherwise Fermat's little theorem and $p-1\mid n-1$ give $a^{n-1}\equiv 1$, so again $a^n\equiv a$. Since the prime divisors are distinct and pairwise coprime, their product $n$ divides $a^n-a$. This is the proof of Korselt criterion:

If $n=pq$ for distinct odd primes with $p<q$, the condition at $q$ would require $q-1\mid pq-1$. Reducing $pq-1$ modulo $q-1$ gives $p-1$, so $q-1\mid p-1$. But $0<p-1<q-1$, which is impossible. Thus a product of two distinct odd primes is not Carmichael.

For $n=pqr$, squarefreeness is automatic. Since $p\equiv 1(\mathrm{mod}p-1)$,Apply the analogous reductions at $q$ and $r$ to obtainFinally $1729=7\cdot 13\cdot 19$, with distinct odd prime factors, andAll three divisibilities hold, so 1729 is a Carmichael number.

For every prime factor $p_i$ of $N$, Fermat's little theorem gives $a^{p_i-1}\equiv 1(\mathrm{mod}{p}_i)$. Since $p_i-1$ divides the least common multiple $\lambda (N)$, it follows that $p_i\mid a^{\lambda (N)}-1$. The primes are distinct and hence pairwise coprime, so their product divides this integer. ThusFor the specified product, $N=1729$ and $\lambda (N)=\mathrm{lcm}(6,12,18)=36$. Since $N-1=1728=48\cdot 36$, raising the preceding modular congruence to the forty-eighth power proves $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$. This is the defining phenomenon of a Carmichael number.

False. The Carmichael number $561=3\cdot 11\cdot 17$ supplies a counterexample. For every $a$ coprime to $561$, the Fermat little theorem gives $a^{560}\equiv 1$ modulo each of these primes, since $2,10,16$ all divide $560$. The Chinese remainder theorem then gives $a^{560}\equiv 1(\mathrm{mod}561)$. Thus the proposed Fermat primality test can fail to detect a composite for every coprime base.

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.

A Carmichael number is a composite $N$ such that $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$. For $p\mid N$, choose by CRT a number whose residue mod $p$ is a primitive root; its order $p-1$ divides $N-1$. If $p^2\mid N$, choose instead a primitive root modulo $p^2$; then $p(p-1)\mid N-1$, impossible because $p\mid N$. Thus $N$ is square-free. Write $N=pm$. Since $p-1\mid N-1$, also $p-1\mid m-1$; compositeness gives $m>1$, hence $m\ge p$ and $p\le \sqrt{N}$. This is Korselt criterion.

Euler's theorem states that $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$ whenever $\gcd (a,m)=1$, where $\varphi (m)$ counts the invertible residue classes. For each prime-power divisor, the same theorem gives $a^{\varphi (p_i^{e_i})}\equiv 1(\mathrm{mod}{p}_i^{e_i})$. Since the exponent defined in the source is a multiple of every one of these exponents, raising that congruence to the corresponding integer power givesThe prime powers are pairwise coprime, so their product divides $a^{\lambda (m)}-1$, proving the congruence modulo $m$.

For the displayed composite integer,Thus every integer coprime to 561 satisfies $\boxed{a^{560}\equiv 1(\mathrm{mod}561)}$. This is a Carmichael number. The source's prime-power least common multiple need not be the minimal universal exponent for all moduli; for powers of two its definition can exceed the usual Carmichael function. No minimality claim is needed here.

Euler's theorem states that if $\gcd (a,m)=1$, then $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$, where $\varphi$ is Euler's totient function. This includes Fermat's little theorem when $m$ is prime.

For each prime-power factor $p_i^{e_i}$, the integer $\varphi (p_i^{e_i})$ divides the defined least common multiple $\lambda (m)$. Euler's theorem modulo that prime power therefore givesThe prime powers are pairwise coprime, so their product divides $a^{\lambda (m)}-1$. Equivalently the Chinese remainder theorem givesFor the specified composite integer,Raising $a^{80}\equiv 1(\mathrm{mod}561)$ to the seventh power provesThus 561 is a Carmichael number. We use exactly the source's definition of $\lambda$ as the least common multiple of prime-power totients; its validity here does not require replacing it by a smaller exponent at powers of two.

For sufficiency, let $N$ be composite and squarefree, with $p-1\mid N-1$ for every prime factor $p$. For any integer $a$ coprime to $N$, Fermat's little theorem gives $a^{N-1}\equiv 1(\mathrm{mod}p)$ for every such $p$. Their product is $N$, so the Chinese remainder theorem gives the required congruence modulo $N$.

For necessity, first rule out a repeated factor. If $N=p^{k}m$ with $k\ge 2$ and $\gcd (p,m)=1$, the Chinese remainder theorem supplies $a\equiv 1+p(\mathrm{mod}{p}^k)$ and $a\equiv 1(\mathrm{mod}m)$. This $a$ is coprime to $N$. But the binomial theorem givescontradicting the Carmichael number condition. Hence $N$ is squarefree.

Now choose a primitive root $g$ modulo a prime factor $p$. Lift it to a unit modulo $N$ by prescribing $a\equiv g(\mathrm{mod}p)$ and $a\equiv 1(\mathrm{mod}N/p)$. The Chinese remainder theorem applies because $N$ is squarefree. The Carmichael congruence implies $g^{N-1}\equiv 1(\mathrm{mod}p)$. Since $g$ has multiplicative order $p-1$, that order divides $N-1$. This proves the other condition.^[ref]

A mathematician associated with Carmichael numbers and the Carmichael function.^[ref]