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]

For an integer modulus $n\ge 2$ and an integer $a$ with greatest common divisor $\gcd (a,n)=1$, Euler's theorem, also called the Fermat-Euler theorem, statesHere Euler's totient function $\phi (n)$ counts the units in the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$. These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to $n$. The guaranteed return to one permits exponent reduction for units.^[ref]

For a prime number $p$, $\phi (p)=p-1$, recovering Fermat's little theorem in the form $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$. Multiplying by $a$ and separately handling $p\mid a$ gives $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.

Modulo twelve, the units have representatives $1,5,7,11$, so Euler's totient function gives $\phi (12)=4$. Multiplication by five producesThus this permutation has two permutation cycles, each of length two. In particular $5^2\equiv 1(\mathrm{mod}12)$, and the guaranteed return $5^4\equiv 1$ follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles $(1,7,4,13)$ and $(2,14,8,11)$, covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.

There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer $d>1$ divides both $a$ and $n$, then $a^k\equiv 0(\mathrm{mod}d)$ for every $k\ge 1$, so $a^k$ cannot be congruent to one modulo $n$. For example, $\gcd (3,15)=3$ and $3^{\phi (15)}=3^8\equiv 6(\mathrm{mod}15)$, rather than one. Such a base has no multiplicative order modulo that integer modulus.^[ref]

For a unit modulo n $a$ and a nonnegative integer $k$, division with remainder writes $k=q\phi (n)+r$ with $0\le r<\phi (n)$. Euler's theorem then givesThis replaces a potentially enormous exponent by a small remainder. The exponent itself is reduced modulo Euler's totient function, while the powers are reduced modulo $n$: these are different integer moduli.

For a worked modulo-fifteen calculation, seven is coprime to fifteen and $\phi (15)=8$. ThereforeUse exponentiation by squaring on the remaining exponent $5=(101{)}_2$, reducing after each multiplication:Thus $7^{2029}\mathrm{mod}15=7$. Modular exponentiation supplies the computation; Euler's theorem supplies the optional shortening of its exponent. Exponentiation by squaring also works for nonunit bases, without using this shortening.

The guaranteed exponent $\phi (n)$ is a common return exponent and an upper bound on the shortest period; it need not be that period. The multiplicative order $d={\mathrm{ord}}_n(a)$ is the least positive return exponent for the chosen unit. The Carmichael function $\lambda (n)$ is the least positive return exponent that works for every unit. Their precise relation isEither smaller return exponent can replace $\phi (n)$ in exponent reduction for units. Modulo fifteen, ${\mathrm{ord}}_{15}(7)=\lambda (15)=4<8=\phi (15)$, so $2029=507\cdot 4+1$ gives $7^{2029}\equiv 7$ immediately. For base four the multiplicative order is only two, smaller even than $\lambda (15)$. A return at exponent eight alone does not prove that the multiplicative order is eight.^[ref]

If the reduced exponent is zero, the rule gives $a^k\equiv a^0=1$, and still requires a unit. Applying it to the nonunit three would falsely predict $3^8\equiv 3^0=1(\mathrm{mod}15)$; the actual residue is six. For negative exponents, first interpret the power using a modular multiplicative inverse, as in modular exponentiation.

A Fermat witness for an integer $n>1$ is a nonzero residue class represented by $1\le a<n$ for which $a^{n-1}\not\equiv 1(\mathrm{mod}n)$. It proves that $n$ is a composite number by Fermat's little theorem. Here the definition includes nonunits; some conventions restrict Fermat witnesses to bases coprime to $n$. The Fermat primality test can first compute the greatest common divisor: if $1<\gcd (a,n)<n$, it already has a proper factor. A zero residue class is excluded. ^[ref]

Choose a reduced residue system $u_1,\dots ,u_{\phi (n)}$. For a unit modulo n $a$, the bijection $u\mapsto au$ on the unit group has inverse $u\mapsto a^{-1}u$. Comparing products before and after this permutation givesThe product $P$ is a unit; its modular inverse cancels it, proving Euler's theorem. Merely being nonzero would not justify cancellation.^[ref]

In the modulo-twelve example, $P=1\cdot 5\cdot 7\cdot 11=385\equiv 1(\mathrm{mod}12)$. The permuted representatives $5,1,11,7$ have the same product, while the unreduced products $(5\cdot 1)(5\cdot 5)(5\cdot 7)(5\cdot 11)$ equal $5^{4}P$. Equating these products modulo twelve exposes the fourth power without calculating it directly. Using all nonzero congruence classes instead would include nonunits, whose product need not permit cancellation.

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.

The algebraic norm on $\mathbb{Z}[\sqrt{-5}]$ is $N(a+b\sqrt{-5})=a^2+5b^2$ and satisfies multiplicativity of the algebraic norm. The calculation in part (a) therefore gives all elements of norm $9$:If one of these factored into two nonunits, multiplicativity would force both factors to have norm $3$. But the Diophantine equation $a^2+5b^2=3$ has no solution. Hence all six displayed elements are irreducible. This is a standard example in which an irreducible element need not have prime norm.

Polynomial division separates a polynomial into a multiple of a chosen divisor and a smaller polynomial remainder. Given $f,g\in F[X]$ over a field $F$, with $g\ne 0$, there are unique polynomials $q,r$ satisfyingHere $q$ is the polynomial quotient. The bound concerns polynomial degree, rather than the sizes of the coefficients.^[ref]

For an original example over the rational numbers, takePolynomial long division first cancels $2X^3$ by subtracting $2Xg$:Subtracting one more copy of $g$ cancels $X^2$:ThusThe final polynomial remainder has polynomial degree one, below the divisor's polynomial degree two. Multiplying out the last identity checks every coefficient, including the constant term $-2+8=6$.

The polynomial degree bound makes this decomposition useful: it replaces a potentially long polynomial with a short polynomial remainder whenever multiples of $g$ can be discarded. At any root of a polynomial of $g$, those multiples vanish under polynomial evaluation. Repeated polynomial division also drives the Euclidean algorithm for finding a greatest common divisor of polynomials.

The coefficient setting matters. Over a commutative ring, the same existence and uniqueness hold when the divisor's leading coefficient is a unit in a ring. A monic polynomial therefore works over the integers, even though they do not form a field; monic polynomial division over a ring explains why zero divisors cause no difficulty in that case.^[ref]

A nonzero divisor alone is insufficient over the integers. Dividing $X$ by $2X+1$ with an integer polynomial quotient and a constant polynomial remainder would require $1=2c$ for an integer $c$, which is impossible. Over the rational numbers the division instead givesThe obstruction is the nonunit leading coefficient $2$. This example separates existence from uniqueness: over an integral domain, the polynomial degree argument still makes any admissible pair unique, if it exists.