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]

In a principal ideal domain, every nonzero prime ideal is maximal. Indeed, write it as $(p)$ with $p\ne 0$. If $(p)\subseteq (a)$, then $p=ab$. Primality gives $a\in (p)$, hence $(a)=(p)$, or $b\in (p)$, say $b=pc$, in which case cancellation gives $1=ac$ and $(a)=R$.

Thus every prime chain has length at most one. If the principal ideal domain is not a field, choose a nonzero nonunit $a$ and a maximal ideal $\mathfrak{m}\supseteq (a)$. Then $(0)⊊\mathfrak{m}$ is a prime chain of length one, so the Krull dimension is one. A field instead has Krull dimension zero.

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.

A nonunit is an element of a ring with no two-sided multiplicative inverse in that ring. For example, $2$ is a nonunit in the integers, even though multiplication by $2$ obeys the cancellation law. Thus being a nonunit does not imply being a zero divisor.

The set of nonunits need not be an ideal. In $\mathbb{Z}$, both $2$ and $-3$ are nonunits, but their sum $-1$ is a unit. In a commutative local ring, by contrast, the nonunits form its unique maximal ideal.

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.

Suppose, for a contradiction, that the monic irreducible polynomials in the polynomial ring $k[t]$ form a finite list $p_1,\dots ,p_r$. The list is nonempty because $t$ itself is monic and irreducible. PutThis has positive degree, so it is a nonzero nonunit. Every such polynomial over a field has an irreducible polynomial as a factor: repeatedly factor a reducible polynomial, with the positive degrees strictly decreasing until an irreducible factor is reached. Dividing that factor by its leading coefficient makes it monic; call it $q$.

By the assumed completeness of the list, $q=p_j$ for some $j$. But then $p_j$ divides both $F$ and $p_1\cdots p_r$, hence their difference $1$. A positive-degree polynomial cannot divide $1$. This contradiction proves there are infinitely many monic irreducible polynomials over every field. This is the polynomial version of Euclid's theorem; it does not require the field itself to be infinite.

In this localization of a ring, a nonzero fraction $a/b$ with odd $b$ is a unit exactly when $a$ is odd: its reciprocal then has odd denominator; if $a$ is even, an inverse would equate an even integer with an odd one after clearing denominators. Consequently every nonzero element has a unique formHere $r$ is the exponent of $2$ in the numerator of the reduced fraction, its nonnegative 2-adic valuation.

Every nonzero ideal has the form $dR$ by part (c). Write the nonzero integer $d=2^{r}v$ with $v$ odd; since $v$ is a unit, $dR=2^{r}R$. Hence the nonzero proper ideals are exactlyThe zero ideal and $R=2^{0}R$ complete the full list. These ideals are distinct: $2^r$ does not belong to $2^{r+1}R$, since $1/2\notin R$.

The reduction map $a/b\mapsto a\mathrm{mod}2$ is a well-defined surjective ring homomorphism $R\to {\mathbb{F}}_2$ with kernel of a ring homomorphism $2R$; odd denominators reduce to $1$. Thus $R/2R\cong {\mathbb{F}}_2$ is a field, so $2R$ is a prime ideal and $2$ is a prime element. Every nonzero nonunit is associated to $2^r$ with $r\ge 1$. If $r\ge 2$, the factorization $2^r=2\cdot 2^{r-1}$ is into two nonunits, so it is not an irreducible element and therefore not a prime element. We concludeThe failed step in the argument of part (b) is the guarantee that the product plus one is a nonunit and hence has an irreducible factor. Here every prime element is an even fraction, so a product of prime elements plus $1$ is an odd fraction, therefore a unit. Already $2+1=3$ has no prime divisor in this ring. In $k[t]$, positive degree prevented that failure.

The structure theorem for finitely generated modules over a principal ideal domain applies to a Euclidean domain because every Euclidean domain is a principal ideal domain. In invariant-factor form, every finitely generated module $M$ has a decompositionwhere $r\ge 0$, and each $d_i$ is a nonzero nonunit. The rank of a module $r$ is unique and the invariant factors of a finitely generated module $d_i$ are unique up to multiplication by units. The zero module is allowed by taking $r=s=0$.

Every abelian group is a module over $\mathbb{Z}$, and a finite abelian group is finitely generated. Since $\mathbb{Z}$ is a Euclidean domain, the theorem applies. A nonzero free module summand would be infinite, so a finite group has $r=0$. Choosing positive integer representatives gives the finite abelian classificationThe ordered integers $d_i$ are uniquely determined. Splitting each $d_i$ into prime powers using the Chinese remainder theorem gives the equivalent elementary-divisor form as a direct sum of cyclic prime-power groups.

The Krull dimension of a commutative ring $R$ isThe length of a prime chain counts strict inclusions, rather than the number of prime ideals.

Let $R$ be a principal ideal domain that is not a field. We first show that every nonzero prime ideal is a maximal ideal. Write such a prime ideal as $P=(p)$ with $p\ne 0$, and suppose $P\subseteq (a)$. Then $p=ab$ for some $b\in R$. Since $ab\in P$, either $a\in P$, in which case $(a)=P$, or $b\in P$. In the second case $b=pc$ for some $c$, and $p=apc$ gives $1=ac$ by multiplicative cancellation in an integral domain. Thus $(a)=R$. This proves maximality.

Since $R$ is an integral domain, $(0)$ is a prime ideal, and every other prime ideal is maximal. Consequently every prime chain has length at most one. For the opposite inequality, choose a nonzero nonunit $a$, which exists because $R$ is not a field. The proper principal ideal $(a)$ is contained in a maximal ideal $\mathfrak{m}$; existence follows from Zorn's lemma applied to the proper ideals containing $(a)$. A maximal ideal is a prime ideal, since its quotient ring is a field. Therefore $(0)⊊\mathfrak{m}$ is a prime chain of length one. Thus the Krull dimension of a principal ideal domain that is not a field is

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.

We prove the stated Eisenstein criterion directly. Assume $n\ge 1$. Suppose $f=gh$ in the polynomial ring $R[X]$. Since the principal ideal domain $R$ is an integral domain, polynomial degree is additive under polynomial multiplication, and the product of the leading coefficients of $g,h$ is the leading coefficient $1$ of $f$. These two coefficients are therefore units. Multiplying $g$ and $h$ by inverse units, without changing their product, makes both factors monic polynomials.

If either factor is a constant polynomial, that factor is now $1$, so the original factor was a unit. It remains to rule out $r=\mathrm{deg}g>0$ and $s=\mathrm{deg}h>0$.

The prime element $p$ generates a maximal ideal in the principal ideal domain $R$. Indeed, if $(p)\subseteq (d)$, then $p=de$, and the irreducible element property of $p$ forces either $(d)=R$ or $(d)=(p)$. Consequently $k=R/(p)$ is a field. Apply reduction modulo an ideal to every coefficient. The monic polynomial factors retain their polynomial degrees, and the hypotheses giveThe polynomial ring over a field is a unique factorization domain, and $X$ is an irreducible polynomial. Thus its only monic polynomial divisors in $X^n$ are powers of $X$. Hence $\overline{g}=X^r$ and $\overline{h}=X^s$. Both have zero constant term, so $p\mid g(0)$ and $p\mid h(0)$. This gives $p^2\mid g(0)h(0)=a_0$, a contradiction.

The monic polynomial $f$ has positive polynomial degree, so it is a nonzero nonunit. Every factorization therefore has a unit factor, proving

No such property exists. The ring isomorphism in part (b)(ii) identifies quotient rings by elements having different irreducible element behaviour.

The element $X^3$ is an irreducible element of $T$. It is nonzero and a nonunit. Every nonzero nonunit of $T$ has polynomial degree at least $2$: the only possible polynomials of smaller polynomial degree are constant polynomials, and every nonzero constant polynomial is a unit. If $X^3=uv$ with $u,v\in T$ both nonunits, additivity of polynomial degree in the integral domain $\mathbb{R}[X]$ would givewhich is impossible. Thus one factor must be a unit.

In $\mathbb{R}[Y]$, however, $Y^3=Y\cdot Y^2$ is a product of two nonunits, so $Y^3$ is not an irreducible element. If a ring isomorphism invariant $P$ characterized irreducible elements by the indicated quotient ring, the irreducible element $X^3\in T$ would imply that $T/(X^3{)}_T$ has $P$. Its isomorphic quotient ring $\mathbb{R}[Y]/(Y^3)$ would then have $P$, incorrectly making $Y^3\in \mathbb{R}[Y]$ an irreducible element.

Consequently,

The required property isFor a nonzero element $x$ of an integral domain $R$, this follows fromIndeed, $\overline{a}\overline{b}=0$ in the quotient ring exactly when $x\mid ab$. The prime element condition says this forces $x\mid a$ or $x\mid b$, exactly the absence of zero divisors in the quotient ring. The nonunit condition makes the quotient ring nonzero. Being an integral domain is preserved by every ring isomorphism.

With the usual definition of a prime element, $x\ne 0$ is understood. The prime ideal formulation works for every ideal of any commutative ring, including the zero ideal; it avoids this convention about elements.

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.

A unit in a unital ring $R$ is an element $u$ with a two-sided multiplicative inverse $v\in R$:The ring is part of the condition. In $\mathbb{Z}$ the only units are $1$ and $-1$, whereas every nonzero rational number is a unit in $\mathbb{Q}$. Modulo six, $5$ is a unit because $5\cdot 5\equiv 1(\mathrm{mod}6)$, while $2$ is a nonunit.

In a nonzero ring, zero is never a unit, since $0v=0\ne 1$. Every unit has multiplicative cancellation, but a cancellable element need not be a unit: $2$ can be cancelled in the integers, yet its reciprocal is not an integer. The units form the unit group of the ring.