Divisibility in integral domains

StructureIrreducible element #

An irreducible element of a commutative ring or monoid is a non-unit that cannot be split as a product of two non-units: whenever it is written as a product, one of the factors is a unit. Irreducible elements play the role that prime numbers play among the natural numbers, as the smallest building blocks of multiplication. They are the elements that appear in factorizations, and the question of when such factorizations are unique leads to the theory of unique factorization domains.

Definition

Let $M$ be a monoid, written multiplicatively, and recall that a unit of $M$ is an element with a two-sided inverse. An element $p$ of $M$ is irreducible when

$p$ is not a unit, and
whenever $p = ab$ with $a, b \in M$, at least one of $a$ and $b$ is a unit.

Equivalently, $p$ is irreducible exactly when it is not a unit and every factorization of $p$ has a unit factor. In an integral domain $R$ the usual textbook definition asks in addition that $p \neq 0$, but this is automatic: if $0$ were irreducible, the factorization $0 = 0 \cdot 0$ would force $0$ to be a unit, contradicting the first condition. So an irreducible element of a monoid with zero is never zero.

Irreducibility depends only on $p$ up to units. Two elements $p$ and $q$ of a commutative monoid are associated if $q = pu$ for a unit $u$, and an element associated with an irreducible element is again irreducible. For instance $p$ is irreducible in $\mathbb{Z}$ if and only if $-p$ is.

Examples

Natural numbers. In the multiplicative monoid of the natural numbers the only unit is $1$, and the irreducible elements are exactly the prime numbers.
Integers. The units of $\mathbb{Z}$ are $\pm 1$, so the irreducible elements of the integers are the numbers $\pm p$ with $p$ a prime number.
Polynomials over a field. If $K$ is a field, the units of $K[X]$ are the nonzero constants, and every polynomial of degree $1$ is irreducible. Over a field, a polynomial of degree $2$ or $3$ is irreducible exactly when it has no root in the field, since any nontrivial factorization would include a factor of degree $1$. So $X^2 + 1$ is irreducible over $\mathbb{R}$, while over the complex numbers it factors as $(X - i)(X + i)$. Over an algebraically closed field, every irreducible polynomial has degree $1$.
Gaussian integers. A prime number need not stay irreducible in a larger ring. In $\mathbb{Z}[i]$ one has $2 = (1 + i)(1 - i)$ and $5 = (2 + i)(2 - i)$, with no factor a unit, while $3$ remains irreducible. In fact a prime number that is not irreducible in $\mathbb{Z}[i]$ is a sum of two squares, which is one route to the two-squares theorem.
Non-examples. Units, and in particular $1$, are never irreducible; neither is $0$ in a ring. A power is never irreducible unless the exponent is $1$: for $n \neq 1$, the element $x^n$ is not irreducible.

Irreducible and prime elements

A prime element $p$ of a commutative ring is a nonzero non-unit such that $p \mid ab$ implies $p \mid a$ or $p \mid b$. In an integral domain every prime element is irreducible: if $p = ab$, then $p$ divides $a$ or $b$, say $a = pc$, and cancelling $p$ from $p = pcb$ shows that $b$ is a unit.

The converse fails in general. In the ring $\mathbb{Z}[\sqrt{-5}]$, consider the norm $N(a + b\sqrt{-5}) = a^2 + 5b^2$, which is multiplicative. The elements of norm $1$ are exactly the units $\pm 1$, so a factorization of $2$, of norm $4$, into two non-units would need two factors of norm $2$. No element has norm $2$ (nor $3$), so $2$ is irreducible. Yet $$2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}),$$ and $2$ divides neither factor on the right, so $2$ is not prime. The same equation shows that $6$ has two essentially different factorizations into irreducibles.

The converse does hold in the rings of most interest. In a unique factorization domain, an element is irreducible if and only if it is prime; indeed this equivalence, together with the existence of factorizations, characterizes such domains. More generally, call $a$ primal if whenever $a \mid bc$ one can write $a = a_1 a_2$ with $a_1 \mid b$ and $a_2 \mid c$; in a cancellative commutative monoid with zero in which every element is primal, such as a GCD domain, irreducible and prime elements coincide.

Properties

Existence of factorizations. In a commutative monoid with zero with no infinite sequence $a_1, a_2, \dots$ of nonzero elements in which each $a_n = a_{n+1} x_n$ for a non-unit $x_n$, every nonzero element is a product of irreducible elements, up to a unit factor. This applies to every Noetherian integral domain.
Maximal ideals. In a principal ideal domain, a nonzero element $p$ is irreducible if and only if the ideal $(p)$ is maximal (see maximal ideal). For a field $K$ this means that $K[X]/(f)$ is a field exactly when $f$ is irreducible, the basis of the construction of the rupture field.
Divisibility between irreducibles. If $p$ and $q$ are irreducible and $p$ divides $q$, then $q$ divides $p$. Indeed, writing $q = pu$, irreducibility of $q$ and the fact that $p$ is not a unit force $u$ to be a unit, so $p$ and $q$ are associated.

Tests for irreducibility of polynomials include Eisenstein's criterion and reduction modulo a prime. The minimal polynomial of an algebraic element over a field is irreducible. In a principal ideal domain, two elements that are not both zero are coprime exactly when they have no irreducible common factor, that is, when their greatest common divisor is a unit.

In Mathlib

Mathlib defines irreducibility for an arbitrary monoid, which need not be commutative or have a zero element, as a structure recording the two conditions: not a unit, and a unit factor in every factorization. It deliberately leaves out the condition $p \neq 0$, which would require a zero element; in a monoid with zero it follows as a lemma. The same definition therefore serves rings, the natural numbers under multiplication, and monoids of associated classes, and Mathlib also has an additive version, written out separately and paired with it so that lemmas transfer between the two. Mathlib's prime numbers are defined as the irreducible elements of the natural numbers, which makes the natural-number example hold by definition. Prime elements form a separate notion, and Mathlib's unique factorization monoids are required to satisfy the equivalence of the two as one of their axioms.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibIrreducible

Uses 1 · Used by 27

Statement usesRing

DefinitionCoprime element #

Two elements $x$ and $y$ of a commutative ring are coprime when $1$ can be written as a combination $ax + by$ with coefficients $a, b$ in the ring. For the integers this is the familiar condition that the greatest common divisor is $1$, by Bézout's identity. In a general ring it is a stronger condition than having no common non-unit factor, and it is the form of coprimality that appears in results such as the Chinese remainder theorem: it says that the ideals generated by $x$ and $y$ together generate the whole ring, which is the hypothesis of that theorem.

Definition

Let $R$ be a commutative ring and $x, y \in R$. Then $x$ and $y$ are coprime if there exist $a, b \in R$ with $ax + by = 1$. The definition is symmetric: $x$ and $y$ are coprime exactly when $y$ and $x$ are.

In terms of ideals, $x$ and $y$ are coprime if and only if the principal ideals $(x)$ and $(y)$ satisfy $(x) + (y) = R$, since $(x) + (y)$ consists of all combinations $ax + by$ and an ideal is all of $R$ exactly when it contains $1$.

Examples

Integers. Two integers are coprime if and only if their greatest common divisor is $1$. For instance $4$ and $9$ are coprime, as $(-2)\cdot 4 + 1 \cdot 9 = 1$, while $4$ and $6$ are not, since every combination $4a + 6b$ is even.
Units and zero. The element $1$ is coprime to every element. An element is coprime to $0$ if and only if it is a unit, and coprime to itself if and only if it is a unit.
Fields. In a field, and more generally in a semifield (a commutative semiring with $0 \neq 1$ in which every nonzero element has an inverse), two elements are coprime if and only if they are not both zero.
Polynomials in two variables. In the polynomial ring $k[X, Y]$ over a field $k$, the only common divisors of $X$ and $Y$ are the nonzero constants, which are units. Yet $X$ and $Y$ are not coprime: every combination $aX + bY$ has constant term $0$. Likewise the only common divisors of $2$ and $X$ in the polynomial ring $\mathbb{Z}[X]$ are $\pm 1$, yet they are not coprime, because the constant term of $2a + Xb$ is even.

Properties

Throughout, $x$, $y$, $z$ are elements of a commutative ring.

Common divisors. If $x$ and $y$ are coprime, then every common divisor of $x$ and $y$ is a unit: if $d$ divides both, it divides $ax + by = 1$.
Euclid's lemma. If $x$ and $y$ are coprime and $x$ divides $yz$, then $x$ divides $z$. Indeed $z = axz + byz$, and $x$ divides both terms.
Products of divisors. If $x$ and $y$ are coprime and both divide $z$, then $xy$ divides $z$.
Products and powers. The product $xy$ is coprime to $z$ if and only if both $x$ and $y$ are coprime to $z$. Consequently, if $x$ and $y$ are coprime, then $x^m$ and $y^n$ are coprime for all natural numbers $m$ and $n$.
Euclidean steps. For every $z$, $x + yz$ is coprime to $y$ if and only if $x$ is, so in a Euclidean domain the steps of the Euclidean algorithm do not change whether two elements are coprime.
Ring morphisms. If $x$ and $y$ are coprime and $f$ is a ring morphism, then $f(x)$ and $f(y)$ are coprime, since $f(a)f(x) + f(b)f(y) = f(1) = 1$.

Relation to greatest common divisors

Call $x$ and $y$ relatively prime when every common divisor is a unit; in a ring with greatest common divisors this says that $\gcd(x, y)$ is a unit. The first property above shows that coprime elements are relatively prime, and the polynomial examples show that the converse fails in general. The converse does hold when the ideal $(x, y)$ is principal, generated by some $d$: then $d$ divides $x$ and $y$, so a relatively prime pair forces $d$ to be a unit and $(x, y) = R$. Thus, when the ideal generated by $x$ and $y$ is principal, $x$ and $y$ are relatively prime if and only if they are coprime. In particular the two notions agree in every principal ideal domain, such as $\mathbb{Z}$ or the polynomial ring $k[X]$ over a field.

Coprime ideals

The ideal form of the definition extends to arbitrary ideals: two ideals $I$ and $J$ of $R$ are coprime, or comaximal, when $I + J = R$ (Mathlib states this as the same combination condition in the semiring of ideals; the two agree, as noted below). Two elements are coprime exactly when the principal ideals they generate are coprime. For example, two distinct maximal ideals are coprime (see maximal ideal). The Chinese remainder theorem says that for pairwise coprime ideals $I_1, \dots, I_n$, the quotient of $R$ by their intersection is isomorphic to the product of the quotients $R/I_k$.

In Mathlib

Mathlib defines coprimality for commutative semirings, not only rings, by the same condition that some combination $ax + by$ equals $1$. Since the ideals of a commutative semiring themselves form a commutative semiring, the same definition applies to ideals, and Mathlib proves that ideals $I$ and $J$ are coprime in this sense if and only if $I + J = R$. In a semiring without negatives the definition can be too strict: for natural numbers it holds only when one of the two numbers is $1$. Mathlib therefore keeps a separate notion for natural numbers, greatest common divisor equal to $1$, and proves that natural numbers satisfy it exactly when their images in the integers are coprime.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibIsCoprime

Uses 2 · Used by 4

Statement usesRing · Ideal of a commutative ring

Used byChinese remainder theorem · Separable polynomial · Mason–Stothers theorem · Ostrowski's theorem

ClassUnique factorisation domain #

A unique factorisation domain (UFD) is an integral domain in which every nonzero non-unit is a product of irreducible elements, and this product is unique up to the order of the factors and multiplication of the factors by units. It is the setting in which the fundamental theorem of arithmetic generalises: the integers, polynomial rings over fields, and polynomial rings over the integers all have unique factorisation, and in such rings greatest common divisors, coprimality and divisibility can be read off from factorisations exactly as for whole numbers.

Definition

Let $R$ be an integral domain, that is, a nonzero commutative ring without zero divisors. Two elements $a, b$ are associated if $b = au$ for a unit $u$. Then $R$ is a unique factorisation domain if

every nonzero non-unit $a$ can be written as $a = p_1 p_2 \cdots p_m$ with each $p_i$ irreducible, and
whenever $p_1 \cdots p_m = q_1 \cdots q_n$ with all $p_i$ and $q_j$ irreducible, then $m = n$ and, after reordering, each $p_i$ is associated with $q_i$.

Allowing an extra unit factor, the first condition says that every nonzero element is associated with a product of irreducibles (the empty product $1$ covers the units). An integral domain with both properties is a UFD in the sense of Mathlib's definition: existence and uniqueness of irreducible factorisations imply unique factorisation. Conversely, in a UFD every nonzero element is associated with a product of prime elements, which are in particular irreducible, and two finite families of irreducible elements with associated products can be matched up so that corresponding elements are associated.

An equivalent definition uses prime elements, the nonzero non-units $p$ such that $p \mid ab$ implies $p \mid a$ or $p \mid b$: an integral domain is a UFD if and only if every nonzero element is associated with a product of prime elements. Factorisations into primes are automatically unique, since a prime dividing a product of primes must be associated with one of them and can be cancelled.

Examples

Principal ideal domains. Every principal ideal domain is a UFD (see principal ideal domain). Since every Euclidean domain is a principal ideal domain (see Euclidean domain), this covers the integers, the Gaussian integers $\mathbb{Z}[i] = \{a + bi : a, b \in \mathbb{Z}\}$, and the polynomial ring $K[X]$ over a field $K$. Fields are UFDs trivially, since they have no nonzero non-units.
Natural numbers. The multiplicative monoid of the natural numbers is not a ring, but it satisfies Mathlib's unique factorisation axioms; this is the fundamental theorem of arithmetic.
Polynomial rings. If $D$ is a UFD, then so is the polynomial ring $D[X]$, and, more generally, the ring of polynomials over $D$ in any set of variables, finite or infinite, is a UFD (see polynomial in several indeterminates). Thus $\mathbb{Z}[X]$ and $K[X, Y]$ are UFDs, although neither is a principal ideal domain: the ideals $(2, X)$ and $(X, Y)$ are not principal.
A non-example. In $\mathbb{Z}[\sqrt{-5}]$ the elements $2$, $3$ and $1 \pm \sqrt{-5}$ are irreducible, and $$6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$$ are two factorisations of $6$ in which no factor on the left is associated with a factor on the right. So $\mathbb{Z}[\sqrt{-5}]$ is not a UFD, although it is Noetherian and so every nonzero non-unit does have some factorisation into irreducibles.

Properties

Irreducible equals prime. In a UFD an element is irreducible if and only if it is prime. In any integral domain every prime element is irreducible, but the converse can fail, as the element $2$ of $\mathbb{Z}[\sqrt{-5}]$ shows.
Greatest common divisors. Taking the smaller exponent of each prime factor shows that every UFD has greatest common divisors and least common multiples (see greatest common divisor).
Integral closure. A UFD is integrally closed in its field of fractions (see field of fractions): a fraction in lowest terms that is a root of a monic polynomial with coefficients in the ring has a unit denominator. This generalises the irrationality of $\sqrt{2}$.
Kaplansky's criterion. An integral domain is a UFD exactly when each of its nonzero prime ideals contains a prime element (see prime ideal).
Noetherian domains. In a Noetherian integral domain there is no infinite sequence of elements in which each element is nonzero and divides the one before with a non-unit cofactor, so factorisations into irreducibles exist. A Noetherian domain is therefore a UFD exactly when its irreducibles are prime; equivalently, a Noetherian domain is a UFD if and only if every prime ideal of height one, that is, every nonzero prime ideal containing no smaller nonzero prime ideal, is principal.
Dedekind domains. A Dedekind domain is a Noetherian, integrally closed integral domain in which every nonzero prime ideal is maximal. A Dedekind domain that is a UFD is a principal ideal domain, and a Dedekind domain with finite class group is a principal ideal domain exactly when its class number, the order of that group, is $1$. The ring of integers of a number field is a Dedekind domain with finite class group, so it has unique factorisation of elements exactly when its class number is $1$.

The main classes of integral domains form a chain of inclusions: Euclidean domains, principal ideal domains, unique factorisation domains, GCD domains, and integrally closed domains. Each inclusion is strict; for example, the ring of all algebraic integers has greatest common divisors but no irreducible elements at all (every algebraic integer is the square of one), although it has nonzero non-units such as $2$, so it is not a UFD. Unique factorisation of nonzero ideals into prime ideals, rather than of elements, characterises Dedekind domains, and Eisenstein's criterion is a test for irreducibility in polynomial rings, most often applied over a UFD such as the integers.

In Mathlib

Mathlib defines unique factorisation for a commutative monoid with zero rather than for a ring, and with different axioms: cancellation by nonzero elements, the absence of infinite chains of proper divisors described above, and the equivalence of irreducible and prime elements. These are equivalent to the textbook conditions, and the existence of factorisations follows from them: every nonzero element is associated with a product of prime elements. Uniqueness is stated for unordered lists with repetition, matched up to association. A unique factorisation domain is a commutative ring that is an integral domain and satisfies this class; the class alone does not exclude the zero ring, since a monoid with zero that has only one element satisfies it. The same class covers the natural numbers under multiplication, which form no ring.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibUniqueFactorizationMonoid

Uses 3 · Used by 5

Statement usesRing · Irreducible element · Prime numbers

Used byThe Fundamental Theorem of Arithmetic · $A[{X_i}]$ is a UFD when $A$ is a UFD · Eisenstein's criterion · Integral root theorem · Rational root theorem

AbbreviationGreatest common divisor #

The greatest common divisor of two elements $a$ and $b$ is a common divisor of $a$ and $b$ that every other common divisor divides. For integers not both zero, the largest integer dividing both is a greatest common divisor, so that $\gcd(12, 18) = 6$. It governs when fractions can be reduced, when linear equations $ax + by = c$ have integer solutions, and when two elements share no common factor. The same notion makes sense in any commutative ring, and in an integral domain a greatest common divisor, when it exists, is determined up to multiplication by a unit.

Definition

Let $R$ be an integral domain, or more generally a cancellative commutative monoid with zero (one in which $ab = ac$ with $a \ne 0$ implies $b = c$). An element $d$ of $R$ is a greatest common divisor of $a$ and $b$ if

$d$ divides $a$ and $d$ divides $b$, and
every $c$ that divides both $a$ and $b$ also divides $d$.

"Greatest" refers to divisibility, not to size. If $d$ and $d'$ are both greatest common divisors of $a$ and $b$, each divides the other, so they are associated: $d' = ud$ for a unit $u$. Conversely every associate of a greatest common divisor is again one. The greatest common divisor is therefore determined only up to a unit, and a choice of normal form singles out one representative: the nonnegative one in $\mathbb{Z}$, the monic one (or $0$) in a polynomial ring over a field. A domain in which every pair of elements has a greatest common divisor is called a GCD domain, and in Mathlib the greatest common divisor operation is a choice of such an element for each pair.

In $\mathbb{Z}$ the two descriptions agree. For $a$ and $b$ not both zero, the largest common divisor is positive and is divisible by every common divisor; and $\gcd(0, 0) = 0$, since every integer divides $0$.

Examples

$\gcd(12, 18) = 6$ and $\gcd(-4, 6) = 2$; the sign of the arguments plays no role.
$\gcd(a, 0)$ is $a$ up to a unit, and $\gcd(a, 1)$ is a unit, normalized to $1$.
Over $\mathbb{Q}$, since $x^2 - 1 = (x - 1)(x + 1)$ and $x^2 - 3x + 2 = (x - 1)(x - 2)$, the monic greatest common divisor of these two polynomials is $x - 1$.
In $\mathbb{Z}[\sqrt{-5}]$ the elements $6$ and $2 + 2\sqrt{-5}$ have no greatest common divisor. Both $2$ and $1 + \sqrt{-5}$ divide each of them, so a greatest common divisor $d$ would have norm divisible by $4$ and by $6$, while dividing $6$ and $2 + 2\sqrt{-5}$ forces its norm to divide $36$ and $24$. The norm would be $12$, but $x^2 + 5y^2 = 12$ has no integer solutions.

Properties

Fix a domain in which greatest common divisors exist, with a chosen one for each pair.

An element divides $\gcd(a, b)$ if and only if it divides both $a$ and $b$.
$\gcd(a, b) = 0$ if and only if $a = b = 0$.
With normalized values, $\gcd$ is commutative and associative, $\gcd(a, 0)$ is the normal form of $a$, and $\gcd(a, 1) = 1$. Without normalization the same statements hold up to associates, for instance $\gcd(a, b)$ is associated with $\gcd(b, a)$.
$\gcd(ca, cb)$ is associated with $c \gcd(a, b)$.
$\gcd(a, b)$ times the least common multiple of $a$ and $b$ is associated with $ab$ (see least common multiple).
$\gcd(a, b)$ is a unit if and only if every common divisor of $a$ and $b$ is a unit.
In a commutative ring with normalized greatest common divisors, if $a$ divides $b - c$ then $\gcd(a, b) = \gcd(a, c)$. Taking $c$ to be the remainder of $b$ on division by $a$ gives the step of the Euclidean algorithm: for example $\gcd(252, 198) = \gcd(198, 54) = \gcd(54, 36) = \gcd(36, 18) = 18$.

Bézout's identity

In a principal ideal domain the greatest common divisor is a linear combination of the two elements: there are $x$ and $y$ with $\gcd(a, b) = ax + by$. This is Bézout's identity. In ideal-theoretic terms, the ideal generated by $a$ and $b$ is the principal ideal generated by $\gcd(a, b)$. Consequently, in such a domain, $\gcd(a, b)$ is a unit if and only if $ax + by = 1$ for some $x$ and $y$, that is, if and only if $a$ and $b$ are coprime; for integers, $a$ and $b$ are coprime exactly when $\gcd(a, b) = 1$. Running the Euclidean algorithm backwards produces the coefficients: from the example above, $18 = 4 \cdot 252 - 5 \cdot 198$. The extended Euclidean algorithm does this systematically: given natural numbers $a$ and $b$, the integers $x$ and $y$ it returns satisfy $\gcd(a, b) = ax + by$, and the same holds for integers $a$ and $b$, with the algorithm run on their absolute values and the signs adjusted. Both statements need more than the existence of greatest common divisors: in the polynomial ring $\mathbb{Z}[x]$, where they exist, $\gcd(2, x) = 1$ but $1$ is not of the form $2f + xg$.

Existence

In a unique factorization domain two nonzero elements have as a greatest common divisor the product of the common prime factors, each raised to the smaller of its two exponents, and every unique factorization domain carries a greatest common divisor operation. This covers $\mathbb{Z}$, polynomial rings over a field, and every principal ideal domain. Moreover, the polynomial ring over a GCD domain is again a GCD domain. The example of $\mathbb{Z}[\sqrt{-5}]$ shows that existence can fail in an integral domain.

In Mathlib

Mathlib packages the greatest common divisor as a structure on a cancellative commutative monoid with zero. The structure supplies two operations, the greatest common divisor and the least common multiple, together with the axioms that the first divides both arguments, that every common divisor divides it, that their product is associated with the product of the arguments, and that the least common multiple with $0$ is $0$. Because the value is fixed only up to units, general results are stated up to associates; a normalized variant, which requires every value to be in normal form, gives exact equalities such as commutativity. For the integers the value is nonnegative and agrees with the greatest common divisor of their absolute values, computed in the natural numbers; for polynomials over a field, the normal form of a nonzero polynomial is monic. Euclidean domains also carry a separate, computable greatest common divisor defined by the Euclidean algorithm, which is not normalized.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibGCDMonoid.gcd

Uses 1 · Used by 10

Statement usesRing

Used byEuclid's' algorithm · Euler's totient function ($\varphi$) · Arithmetic functions · $A[X]$ has gcd and lcm if $A$ does · $A[{X_i}]$ is a UFD when $A$ is a UFD · Mason–Stothers theorem · Cauchy's theorem (group theory) · Ostrowski's theorem · Bézout's identity · Rational functions

AbbreviationLeast common multiple #

The least common multiple of two elements $a$ and $b$ is a common multiple of both that divides every other common multiple. For nonzero natural numbers it is the smallest positive integer divisible by both, written $\operatorname{lcm}(a, b)$, while $\operatorname{lcm}(a, 0) = 0$; the same idea makes sense in any commutative ring, where it is defined purely in terms of divisibility. It is the counterpart of the greatest common divisor, and for nonzero $a$ and $b$ their product is $ab$ up to a unit, so each determines the other. Least common multiples appear whenever periodic conditions are combined, as in adding fractions over a common denominator or solving simultaneous congruences.

Definition

Let $R$ be a commutative ring, or more generally a commutative monoid with zero, and let $a, b \in R$. An element $m \in R$ is a least common multiple of $a$ and $b$ if

$a \mid m$ and $b \mid m$, and
whenever $a \mid c$ and $b \mid c$, also $m \mid c$.

The word "least" refers to the divisibility order, not to size. If $m$ and $m'$ are both least common multiples, each divides the other, so in an integral domain they differ by a unit factor: a least common multiple, when it exists, is unique up to associates. In the integers the units are $\pm 1$, and one takes the nonnegative choice. Since the only multiple of $0$ is $0$ itself, condition 1 forces $\operatorname{lcm}(a, 0) = 0$.

Least common multiples need not exist. In the ring $\mathbb{Z}[\sqrt{-5}]$ the elements $2$ and $1 + \sqrt{-5}$ have no least common multiple: both divide $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ and $2(1 + \sqrt{-5})$. Write $N(x + y\sqrt{-5}) = x^2 + 5y^2$ for the multiplicative norm. A least common multiple $m$ would be divisible by $2$ and by $1 + \sqrt{-5}$, so $N(m)$ would be divisible by $4$ and by $6$, hence by $12$; and $m$ would divide $6$ and $2(1 + \sqrt{-5})$, so $N(m)$ would divide $36$ and $24$, hence $12$. Thus $N(m) = 12$, but $x^2 + 5y^2 = 12$ has no integer solutions.

Examples

$\operatorname{lcm}(4, 6) = 12$, and $\operatorname{lcm}(12, 18) = 36$.
If $\gcd(m, n) = 1$ then $\operatorname{lcm}(m, n) = mn$ for natural numbers $m$ and $n$.
From prime factorisations: $12 = 2^2 \cdot 3$ and $18 = 2 \cdot 3^2$, and taking the larger exponent of each prime gives $2^2 \cdot 3^2 = 36$. In general, for nonzero natural numbers $a$ and $b$, the exponent of each prime in $\operatorname{lcm}(a, b)$ is the larger of its exponents in $a$ and in $b$.
Over the rationals, $x^2 - 1 = (x - 1)(x + 1)$ and $x^2 + x = x(x + 1)$ have least common multiple $x(x - 1)(x + 1) = x^3 - x$ among polynomials, normalized to be monic.

Properties

Throughout, $R$ is a commutative monoid with zero in which cancellation by nonzero elements holds and every pair of elements has a gcd and an lcm, such as $\mathbb{N}$, $\mathbb{Z}$, or any unique factorisation domain.

Universal property. For all $a, b, c$, $\operatorname{lcm}(a, b) \mid c$ if and only if $a \mid c$ and $b \mid c$. In particular $a$ divides $\operatorname{lcm}(a, b)$, and so does $b$.
Relation with the gcd. The product $\gcd(a, b)\,\operatorname{lcm}(a, b)$ is associated to $ab$, that is, equal to it up to a unit. In $\mathbb{N}$, where the only unit is $1$, this reads $$\gcd(a, b)\,\operatorname{lcm}(a, b) = ab,$$ so $\operatorname{lcm}(a, b) = ab / \gcd(a, b)$ for $a, b$ not both zero. In every case $\operatorname{lcm}(a, b)$ divides $ab$.
Zero. $\operatorname{lcm}(a, b) = 0$ if and only if $a = 0$ or $b = 0$.
Primes. For a prime element $p$, $p \mid \operatorname{lcm}(a, b)$ if and only if $p \mid a$ or $p \mid b$.
Algebraic laws. Once the lcm is normalized to a canonical representative (nonnegative integers, monic polynomials), it is commutative and associative, so the least common multiple of a finite set is well defined, and it divides $c$ exactly when every member of the set does.
Congruences. For natural numbers $a, b, m, n$, $a \equiv b \pmod m$ and $a \equiv b \pmod n$ hold together if and only if $a \equiv b \pmod{\operatorname{lcm}(m, n)}$. This underlies the uniqueness part of the Chinese remainder theorem, and it holds without any coprimality assumption.

Ideals and existence

In an integral domain, $c$ is a common multiple of $a$ and $b$ exactly when $c$ lies in the ideal $(a) \cap (b)$, so a least common multiple exists precisely when this intersection is principal, and then it generates it. In a Euclidean domain, for instance, $(a) \cap (b) = (\operatorname{lcm}(a, b))$. The same holds in every principal ideal domain, and in a unique factorisation domain the lcm is built from factorisations by taking maximal exponents, so every unique factorisation domain has gcds and lcms. In an integral domain, every pair of elements has a gcd if and only if every pair has an lcm (for a single pair of nonzero elements, an lcm $m$ yields the gcd $ab/m$, but not conversely).

The greatest common divisor is the dual notion, the greatest lower bound in the divisibility order where the lcm is the least upper bound.
When $\gcd(a, b)$ is a unit, the lcm is the product $ab$ up to a unit. This applies in particular to coprime elements, those with $xa + yb = 1$ for some $x$ and $y$.
For ideals, the role of the lcm is played by the intersection. In a Dedekind domain the ideals themselves have gcds and lcms, and there the lcm of two ideals is their intersection.
If a ring has gcds and lcms, so does its polynomial ring.

In Mathlib

For general commutative monoids, Mathlib treats the least common multiple as one of the two operations of a gcd monoid, a structure on a cancellative commutative monoid with zero. The structure takes the gcd as primary and asks of the lcm only that $\gcd(a, b)\operatorname{lcm}(a, b)$ be associated to $ab$ and that the lcm with $0$ be $0$; the universal property is then a theorem. Because the operation is only determined up to units, many identities hold in general only up to association, and exact equalities such as commutativity need the normalized variant, which picks a canonical representative in each class of associates. On the natural numbers the operation is the usual lcm, and on the integers it is always nonnegative. The lcm of a finite set is defined by folding the binary operation, with the empty set giving $1$.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibGCDMonoid.lcm

Uses 3 · Used by 5

Statement usesNatural number · Integer · Ring

Used by$A[X]$ has gcd and lcm if $A$ does · Mason–Stothers theorem · Cauchy's theorem (group theory) · Ostrowski's theorem · Rational functions

ClassPrincipal ideal domain #

A principal ideal domain, or PID, is an integral domain in which every ideal is generated by a single element. The integers and the polynomials in one variable over a field are the standard examples. In a PID the arithmetic of the integers carries over almost unchanged: greatest common divisors exist and satisfy Bézout's identity, irreducible elements are prime, and every nonzero nonunit factors into irreducibles, uniquely up to order and units. Finitely generated modules over a PID also have a complete and explicit classification, as direct sums of cyclic modules.

Definition

Let $R$ be a commutative ring. An ideal $I$ of $R$ is principal if $I = (a) = \{ra : r \in R\}$ for some element $a$ of $R$, that is, if $I$ is the ideal generated by one element. The ring $R$ is a principal ideal ring if every ideal of $R$ is principal, and a principal ideal domain if moreover it is an integral domain: $1 \neq 0$ and $ab = 0$ forces $a = 0$ or $b = 0$.

Principal ideals translate divisibility into inclusion. For elements $x$ and $y$ of $R$, $(x) \subseteq (y)$ holds exactly when $y$ divides $x$, and in an integral domain $(x) = (y)$ holds exactly when $x$ and $y$ are associates, that is, when $x = uy$ for a unit $u$. So the ideals of a PID correspond to its elements taken up to multiplication by units.

Examples

Fields. A field has only the ideals $0 = (0)$ and $(1)$, so every field is a principal ideal ring.
Euclidean domains. Every Euclidean domain is a principal ideal ring, hence a PID: in a nonzero ideal $I$ choose a nonzero element $m$ of least size under the Euclidean function; dividing any $x \in I$ by $m$ leaves a remainder that lies in $I$ and is smaller than $m$, hence zero, so $I = (m)$. This covers the integers, the polynomial ring $K[X]$ over a field $K$, and the Gaussian integers $\mathbb{Z}[i]$. The converse fails: the ring $\mathbb{Z}[(1 + \sqrt{-19})/2]$ is a PID that admits no Euclidean function.
Non-examples. In $\mathbb{Z}[X]$ the ideal $(2, X)$ is not principal: a generator would be a common divisor of $2$ and $X$, and the only such divisors are $\pm 1$, yet every element of $(2, X)$ has even constant term. Similarly $(X, Y)$ is not principal in $K[X, Y]$, and $(2, 1 + \sqrt{-5})$ is not principal in $\mathbb{Z}[\sqrt{-5}]$.

Properties

Noetherian. Each ideal is generated by one element, hence finitely generated, so every principal ideal ring is Noetherian (see Noetherian ring).
Greatest common divisors. In a PID, the ideal $(a, b)$ is principal, and its generators are exactly the greatest common divisors of $a$ and $b$: $(a, b) = (\gcd(a, b))$. Consequently $\gcd(a, b) = ax + by$ for some $x, y \in R$, which is Bézout's identity.
Irreducible elements and maximal ideals. In a principal ideal ring, if $p$ is irreducible then $(p)$ is a maximal ideal. In a PID, for $p \neq 0$, $p$ is irreducible if and only if $(p)$ is maximal (see irreducible element and maximal ideal).
Prime ideals. In a principal ideal ring, a nonzero ideal is prime exactly when it is $(p)$ for a prime element $p$, where a nonzero nonunit $p$ is prime if $p \mid ab$ implies $p \mid a$ or $p \mid b$. In a PID every nonzero prime ideal is maximal (see prime ideal). The Krull dimension, the supremum of the lengths of chains of prime ideals, is therefore at most $1$; when $R$ is not a field, a nonzero nonunit lies in a maximal ideal, which gives the chain $0 \subsetneq \mathfrak{m}$ of prime ideals, so a PID that is not a field has Krull dimension exactly $1$.
Unique factorisation. Every PID is a unique factorisation domain (see unique factorisation domain). Factorisations into irreducibles exist because an ascending chain of principal ideals must stabilise, and they are unique because an irreducible $p$ generates a maximal, hence prime, ideal, which makes $p$ a prime element. The converse fails: $\mathbb{Z}[X]$ is a unique factorisation domain but not a PID. For Dedekind domains (Noetherian, integrally closed domains in which every nonzero prime ideal is maximal) the two notions agree: a Dedekind domain with unique factorisation is a principal ideal domain.

Modules over a principal ideal domain

Linear algebra over a field extends to PIDs with one new feature, torsion: an element $m$ of an $R$-module is torsion if $rm = 0$ for some nonzero $r \in R$, and a module is torsion-free if $0$ is its only torsion element. Over a PID, every finitely generated torsion-free module is free, and every submodule of a free module of finite rank is free of finite rank. The structure theorem states that every finitely generated module $M$ over a PID $R$ is isomorphic to a module

\[M \cong R^n \oplus R/(p_1^{e_1}) \oplus \cdots \oplus R/(p_k^{e_k})\]

for some $n \ge 0$, irreducible elements $p_1, \dots, p_k$ and natural numbers $e_1, \dots, e_k$. For $R = \mathbb{Z}$ this classifies finitely generated abelian groups; for $R = K[X]$, applied to a vector space with a linear operator, it yields the rational canonical form and, over an algebraically closed field, the Jordan canonical form.

The classes of rings discussed here are nested: every Euclidean domain is a PID, every PID is a unique factorisation domain, and every unique factorisation domain is integrally closed, with each inclusion strict. A Bézout domain asks only that finitely generated ideals be principal, and a Noetherian Bézout ring is a principal ideal ring. A local PID that is not a field is a discrete valuation ring, and the Dedekind domains are exactly the Noetherian integral domains whose localisations at nonzero prime ideals are discrete valuation rings; in other words, a Dedekind domain is a Noetherian domain whose localisation at every prime ideal is a principal ideal domain.

In Mathlib

Mathlib has no separate class of principal ideal domains. Principality is defined for submodules in general: a submodule is principal when it is spanned by a single element, and an ideal is a submodule of the ring over itself. A principal ideal ring is a semiring, not necessarily commutative, in which every left ideal is principal, and a principal ideal domain is expressed by assuming both that a ring is an integral domain and that it is a principal ideal ring. Results that need less are stated with less: the Noetherian property for any principal ideal ring, and the maximality of the ideal generated by an irreducible element for any commutative one. The results on greatest common divisors are proved for Bézout domains, a larger class than PIDs, relative to any chosen greatest-common-divisor function. A generator of a principal submodule is picked by choice rather than computed.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibSubmodule.IsPrincipal

Uses 3 · Used by 7

Statement usesRing · Ideal of a commutative ring · Generating sets

Used byThe Fundamental Theorem of Arithmetic · Structure of finitely generated abelian groups · Sum of two squares · Structure theorem · Krull's principal ideal theorem · Lie's theorem · Bézout's identity

ClassEuclidean domain #

A Euclidean domain is an integral domain in which one can divide with remainder, the remainder being smaller than the divisor for some measure of size. The integers, every field and the polynomials over a field are the main examples. Division with remainder is exactly what the Euclidean algorithm needs, so in a Euclidean domain greatest common divisors can be computed, every ideal is principal, and factorization into irreducible elements is unique.

Definition

An integral domain $R$, that is, a nonzero commutative ring without zero divisors, is Euclidean if there is a function $f$ from the nonzero elements of $R$ to the natural numbers with the following property: for all $a, b \in R$ with $b \neq 0$ there are $q, r \in R$ such that

\[a = bq + r, \qquad r = 0 \ \text{or}\ f(r) < f(b).\]

The element $q$ is a quotient and $r$ a remainder of $a$ on division by $b$; they need not be unique. Such an $f$ is called a Euclidean function. Many authors also require $f(a) \le f(ab)$ for all nonzero $a$ and $b$. This changes nothing about which rings are Euclidean, since a Euclidean function $f$ can always be replaced by $a \mapsto \min_{c \neq 0} f(ac)$, which has the extra property.

Mathlib's definition of a Euclidean domain is more general in one respect. Instead of a function to the natural numbers it asks for a well-founded relation $\prec$ on $R$, one with no infinite descending chain $\cdots \prec x_2 \prec x_1$. A function $f$ gives such a relation by declaring $x \prec y$ when $f(x) < f(y)$, with $0$ placed below every nonzero element. The structure also carries chosen quotient and remainder operations, written $a / b$ and $a \bmod b$, which satisfy $b\,(a/b) + (a \bmod b) = a$ for all $a$ and $b$ and $(a \bmod b) \prec b$ whenever $b \neq 0$, together with $a/0 = 0$ and the analogue of $f(a) \le f(ab)$: for $b \neq 0$, never $ab \prec a$. Rings that are Euclidean in this wider sense are sometimes called transfinite Euclidean domains, and there are such rings that admit no Euclidean function with values in the natural numbers.

Examples

The integers. The integers form a Euclidean domain with size the absolute value: dividing $a$ by $b \neq 0$ leaves a remainder $r$ with $0 \le r < |b|$. For instance $-7 = 2 \cdot (-4) + 1$.
Fields. Every field is a Euclidean domain: division by a nonzero element is exact, so the remainder on division by any nonzero element is $0$.
Polynomials over a field. For a field $K$, the polynomial ring $K[X]$ is a Euclidean domain, with size the degree; this is polynomial long division.
Gaussian integers. The ring $\mathbb{Z}[i]$ is Euclidean for the norm $N(a + bi) = a^2 + b^2$: given $\alpha$ and $\beta \neq 0$, round each coordinate of $\alpha / \beta \in \mathbb{Q}(i)$ to a nearest integer to get a quotient, and the remainder has norm less than $N(\beta)$, in fact at most $N(\beta)/2$.
Discrete valuation rings. Every discrete valuation ring can be made a Euclidean domain, with size measured by the valuation.
Isomorphic copies. A commutative ring isomorphic to a Euclidean domain is again one.

Properties

Principal ideals. Every ideal of a Euclidean domain is principal, so a Euclidean domain is a principal ideal domain. The zero ideal is $(0)$. If $I$ is a nonzero ideal, well-foundedness gives a nonzero $m \in I$ that is minimal for $\prec$ among the nonzero elements of $I$. For $x \in I$ the remainder $x \bmod m = x - m(x/m)$ lies in $I$ and is smaller than $m$, so it is $0$; hence $m$ divides $x$ and $I = (m)$.
Unique factorization. Since every principal ideal domain is a unique factorization domain, every Euclidean domain is a unique factorization domain.
Divisibility by remainders. The remainder of $a$ on division by $b$ is $0$ exactly when $b$ divides $a$.
The Euclidean algorithm. A greatest common divisor is computed by setting $\gcd(0, b) = b$ and, for $a \neq 0$, $\gcd(a, b) = \gcd(b \bmod a,\ a)$; the recursion ends because the first argument decreases for $\prec$ (see the article on the algorithm). The result divides both $a$ and $b$, and every common divisor of $a$ and $b$ divides it.
Bézout's identity. Keeping track of the quotients along the way, the extended Euclidean algorithm produces $s$ and $t$ with $\gcd(a, b) = as + bt$.
Irreducible elements. If $x$ is irreducible, then for every $y$ either $x$ divides $y$ or $x$ and $y$ are coprime, in the sense that $ux + vy = 1$ for some $u$ and $v$ (see coprime element).

Euclidean domains sit in a chain of classes of integral domains:

\[\text{fields} \subset \text{Euclidean domains} \subset \text{principal ideal domains} \subset \text{unique factorization domains}.\]

Each inclusion is strict. The integers are Euclidean but not a field. The ring $\mathbb{Z}\big[\tfrac{1 + \sqrt{-19}}{2}\big]$ is a principal ideal domain that admits no Euclidean function. The polynomial ring $\mathbb{Z}[X]$ has unique factorization, but its ideal $(2, X)$ is not principal, so it is not Euclidean either. Outside the chain altogether lies $\mathbb{Z}[\sqrt{-5}]$, which lacks unique factorization: $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ are two factorizations into irreducible elements, no two of which are associates (no element has norm $2$ or $3$).

In Mathlib

Mathlib treats a Euclidean domain as a commutative ring equipped with data: chosen quotient and remainder operations and a well-founded relation, rather than the mere existence of a Euclidean function. A ring can therefore carry several Euclidean structures, and the structures Mathlib provides for the integers, fields and polynomial rings are specific choices; for the integers the remainder on division by a nonzero integer is always nonnegative. Division by zero gives $0$ and the remainder on division by $0$ is the element itself. The absence of zero divisors is not an axiom: Mathlib derives from the axioms that a Euclidean domain is an integral domain. The greatest common divisor and the extended Euclidean algorithm are defined as functions on the ring, which needs a way to decide whether two elements are equal (in particular whether an element is $0$); Mathlib takes this decidability as an extra assumption on the ring, which is automatic in classical mathematics.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibEuclideanDomain

Uses 2 · Used by 16

Statement usesRing · Natural number

Used byEuler’s Summation of 1 + (1/2)^2 + (1/3)^2 + …. · Heron’s Formula · Solutions to Pell’s Equation (Freek Wiedijk's 100 theorems) · Greatest Common Divisor Algorithm · Sum of kth powers · Buffon Needle Problem · The Fundamental Theorem of Arithmetic · Change of variables formula · Behrend's construction · Sum of two squares · $K[X]$ is Euclidean · Helly's theorem · Sylvester's law of inertia (uniqueness) · $\Z$ is a Euclidean ring · Cauchy formulas · Holomorphic stability under uniform convergence

DefinitionEuclid's' algorithm #

Euclid's algorithm computes the greatest common divisor of two natural numbers by repeated division with remainder. Its refinement, the extended Euclidean algorithm, also produces integers $x$ and $y$ with $\gcd(a, b) = ax + by$. The algorithm is fast, needs nothing beyond division with remainder, and the coefficients it returns give Bézout's identity in explicit form, inverses in modular arithmetic, and solutions of linear equations in integers.

Definition

Let $a$ and $b$ be natural numbers. Put $r_0 = a$ and $r_1 = b$. As long as the current remainder $r_k$ is nonzero, divide the previous one by it,

\[r_{k-1} = q_k\, r_k + r_{k+1}, \qquad 0 \le r_{k+1} < r_k,\]

which defines the quotient $q_k$ and the next remainder $r_{k+1}$. From $r_1$ on the remainders strictly decrease, so some $r_{n+1}$ is $0$; the algorithm stops at the first such index and returns $r_n$. This is the last nonzero remainder, except when $a = b = 0$ and the output is $0$.

The output is $\gcd(a, b)$. For $b > 0$ the equation $a = qb + r$ shows that a number divides both $a$ and $b$ exactly when it divides both $b$ and $r$, so $\gcd(a, b) = \gcd(b, r)$, where $r$ is the remainder of $a$ modulo $b$. The pair of consecutive remainders therefore keeps the same common divisors at every step, and at the end the pair $(r_n, 0)$ has greatest common divisor $r_n$.

The extended algorithm carries two further sequences alongside the remainders: $s_0 = 1$, $t_0 = 0$, $s_1 = 0$, $t_1 = 1$, and

\[s_{k+1} = s_{k-1} - q_k s_k, \qquad t_{k+1} = t_{k-1} - q_k t_k.\]

By induction $r_k = a s_k + b t_k$ for every $k$, since the same linear recurrence holds for all three sequences. At the last nonzero remainder this reads $\gcd(a, b) = a s_n + b t_n$. In Mathlib the extended algorithm on natural numbers is a function returning a pair of integer coefficients, and its two components $x$ and $y$ satisfy $\gcd(a, b) = ax + by$.

Examples

For $a = 385$ and $b = 133$ the divisions are

\[385 = 2 \cdot 133 + 119, \quad 133 = 1 \cdot 119 + 14, \quad 119 = 8 \cdot 14 + 7, \quad 14 = 2 \cdot 7 + 0,\]

so $\gcd(385, 133) = 7$. The coefficient sequences run $s = 1, 0, 1, -1, 9, -19$ and $t = 0, 1, -2, 3, -26, 55$, and the row of the last nonzero remainder gives

\[7 = 385 \cdot 9 + 133 \cdot (-26).\]

The final row, with remainder $0$, records $0 = 133 \cdot 55 - 385 \cdot 19$, and indeed $19 = 133/7$ and $55 = 385/7$.

To invert $7$ modulo $40$, run the algorithm on $40$ and $7$: the divisions $40 = 5 \cdot 7 + 5$, $7 = 1 \cdot 5 + 2$, $5 = 2 \cdot 2 + 1$ end at remainder $1$, and substituting back gives $1 = 3 \cdot 40 - 17 \cdot 7$. Hence $7 \cdot (-17) \equiv 1 \pmod{40}$, and $23$, the residue of $-17$, is the inverse of $7$ modulo $40$.

Properties

Speed. From the second division on, every two steps the remainder drops below half its earlier value: $r_{k+1} < r_{k-1}/2$ for $k \ge 2$, and also for $k = 1$ when $a \ge b$. The number of divisions is therefore at most about twice the number of binary digits of $b$. Lamé's theorem sharpens this: for $a \ge b \ge 1$ the number of divisions is at most five times the number of decimal digits of $b$. For $a > b \ge 1$, if the algorithm needs $n$ divisions then $a \ge F_{n+2}$ and $b \ge F_{n+1}$, where $F_1 = F_2 = 1$ are the first Fibonacci numbers; consecutive Fibonacci numbers, whose quotients are all $1$ except the last, attain this bound.
Linear combinations. For integers $a$ and $b$, a natural number $n$ can be written as $ax + by$ with integers $x, y$ exactly when $\gcd(a, b)$ divides $n$, and when $a \neq 0$ $\gcd(a, b)$ is the least positive number of this form. Running the extended algorithm on $|a|$ and $|b|$, changing the signs of the two coefficients to match those of $a$ and $b$, and multiplying them by $n/\gcd(a, b)$ solves $ax + by = n$ whenever a solution exists.
Modular inverses. If $n$ and $k$ are coprime and $k > 1$, the coefficient of $n$ in $1 = nx + ky$ reduced modulo $k$ is an inverse of $n$: there is an $m$ with $0 \le m < k$ and $nm \equiv 1 \pmod k$. This is how inverses are computed in practice, and it underlies the constructive proof of the Chinese remainder theorem.
Euclid's lemma. For integers $a$, $b$, $c$, multiplying $1 = ax + cy$ by $b$ shows that if $a$ divides $bc$ and $\gcd(a, c) = 1$, then $a$ divides $b$, the key step towards the uniqueness of prime factorizations.
Continued fractions. For $a, b > 0$ the quotients $q_1, \dots, q_n$ are the partial quotients of the continued fraction of $a/b$; for the example above, $385/133 = 2 + 1/(1 + 1/(8 + 1/2))$.

Generalizations

The algorithm uses only division with remainder, so it runs in every Euclidean domain, where a size function replaces the usual order on remainders. Examples are the integers (a Euclidean domain) and polynomials in one variable over a field. The general version rests on the same step, $\gcd(a, b) = \gcd(b \bmod a, a)$; its output divides both inputs and is divisible by every common divisor. The extended version again returns coefficients with $\gcd(a, b) = a x + b y$. In such a ring the greatest common divisor is determined only up to a unit factor, and the algorithm picks one. For the integers, the coefficients can be read off from those for the absolute values, giving Bézout's identity over the integers. In rings that are not Euclidean, such as polynomials in two variables, a greatest common divisor may exist without being a combination $ax + by$.

In Mathlib

Mathlib runs the extended algorithm on two natural numbers and returns the two coefficients as integers, since one of them is usually negative. The recursion keeps two triples, each a remainder with its two coefficients; each step forms a new triple from the two and drops the older one; the first division divides the second input by the first, so when the first input is the larger one the opening step merely swaps the two. Whatever coefficients the recursion starts from, its final remainder is the greatest common divisor, and started from the triples for the two inputs it returns that divisor together with the coefficient pair. The greatest common divisor of natural numbers comes from Lean's core library, which computes it by the same recursion and sets $\gcd(0, b) = b$. Accordingly, when the first input is $0$ the first coefficient is $0$ and the second is $1$, while for a nonzero first input and second input $0$ the first coefficient is $1$ and the second is $0$. The integer versions reduce to the natural ones by adjusting signs, and the Euclidean-domain versions are separate definitions written for any such ring with decidable equality.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibNat.xgcd

Uses 3 · Used by 3

Statement usesNatural number · Integer · Greatest common divisor

Used byBezout’s Theorem · Focal subgroup theorem · Schur–Zassenhaus theorem

DefinitionEuler's totient function ($\varphi$)#

Euler's totient function, written $\varphi$, assigns to each positive natural number $n$ the number of integers between $1$ and $n$ that are coprime to $n$, that is, share no common factor with $n$ other than $1$. It is one of the basic functions of elementary number theory. It counts the invertible residues modulo $n$, so it is the exponent in Euler's theorem, and it reappears in the theory of cyclic groups, roots of unity and cyclotomic polynomials.

Definition

For a natural number $n \ge 1$,

\[\varphi(n) = \#\{\, a : 1 \le a \le n,\ \gcd(a, n) = 1 \,\},\]

where $\gcd$ is the greatest common divisor. Counting over $0 \le a \le n - 1$ instead gives the same number: the endpoint $n$ is replaced by $0$, and $\gcd(0, n) = \gcd(n, n) = n$, so either endpoint is counted exactly when $n = 1$.

An equivalent description uses modular arithmetic. A residue class $a$ modulo $n$ has a multiplicative inverse exactly when $\gcd(a, n) = 1$ (see $\mathbb{Z}/n\mathbb{Z}$ and its invertible elements), so for $n \ge 1$ the group of units of $\mathbb{Z}/n\mathbb{Z}$ has exactly $\varphi(n)$ elements.

Examples

The first values, for $n = 1, 2, \dots, 12$, are

\[1,\ 1,\ 2,\ 2,\ 4,\ 2,\ 6,\ 4,\ 6,\ 4,\ 10,\ 4.\]

For instance $\varphi(12) = 4$, the integers coprime to $12$ in that range being $1, 5, 7, 11$.

Primes. If $p$ is prime, every integer from $1$ to $p - 1$ is coprime to $p$, so $\varphi(p) = p - 1$. Conversely, a number $p \ge 1$ with $\varphi(p) = p - 1$ is prime.
Prime powers. Among $1, \dots, p^k$ the integers not coprime to $p^k$ are the multiples of $p$, of which there are $p^{k-1}$. Hence, for a prime $p$ and $k \ge 1$, $\varphi(p^k) = p^{k-1}(p - 1)$. For example $\varphi(8) = 4$ and $\varphi(9) = 6$.

Properties

Multiplicativity. If $m$ and $n$ are coprime, then $\varphi(mn) = \varphi(m)\,\varphi(n)$. Thus $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$. Without the coprimality hypothesis one still has $\varphi(\gcd(a, b))\,\varphi(ab) = \varphi(a)\,\varphi(b)\,\gcd(a, b)$ for all natural numbers $a$ and $b$.
Product formula. Combining multiplicativity, the value at prime powers and unique factorization gives Euler's product formula: for every $n \ge 1$, $\varphi(n)$ equals $n$ times the product of $1 - 1/p$ over the distinct primes $p$ dividing $n$, $$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right).$$ For $n = 36$ this is $36 \cdot \tfrac12 \cdot \tfrac23 = 12$.
Divisor sum. Summing $\varphi(d)$ over the divisors $d$ of $n$ gives $n$: $$\sum_{d \mid n} \varphi(d) = n.$$ For $n = 12$ the divisors $1, 2, 3, 4, 6, 12$ contribute $1 + 1 + 2 + 2 + 2 + 4 = 12$.
Size. $\varphi(n) \le n$ for every $n$, and $\varphi(n) < n$ when $n > 1$, since $n$ itself is then not coprime to $n$.
Parity. $\varphi(n)$ is even for $n > 2$: the map $a \mapsto n - a$ pairs the integers coprime to $n$, and no such $a$ equals $n - a$. Consequently $\varphi(n) = 1$ exactly when $n = 1$ or $n = 2$.
Divisibility. If $a$ divides $b$, then $\varphi(a)$ divides $\varphi(b)$.

Proofs of the main formulas

Multiplicativity follows from the Chinese remainder theorem: for coprime $m$ and $n$ the ring $\mathbb{Z}/mn\mathbb{Z}$ is isomorphic to the product $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$, and the units of a product of rings are the pairs of units, so the unit groups have $\varphi(mn)$ and $\varphi(m)\,\varphi(n)$ elements respectively.

For the divisor sum, sort the integers $1, \dots, n$ by their greatest common divisor $d$ with $n$. Those with $\gcd(a, n) = d$ are the numbers $a = db$ with $1 \le b \le n/d$ and $\gcd(b, n/d) = 1$, so there are $\varphi(n/d)$ of them. Summing over the divisors $d$ of $n$ counts every integer once, and as $d$ runs over the divisors of $n$ so does $n/d$.

Applications

Euler's theorem. By Lagrange's theorem applied to the units modulo $n$, $a^{\varphi(n)} \equiv 1 \pmod n$ for every natural number $a$ coprime to $n$. For a prime modulus this is Fermat's little theorem. For example $3^{\varphi(10)} = 3^4 = 81 \equiv 1 \pmod{10}$.
Cyclic groups. In a finite cyclic group of order $n$, for each divisor $d$ of $n$, exactly $\varphi(d)$ elements have order $d$ (see order of an element). Taking $d = n$, such a group has $\varphi(n)$ generators.
Roots of unity. In an integral domain that contains a primitive $k$-th root of unity, there are exactly $\varphi(k)$ primitive $k$-th roots of unity.
Cyclotomic polynomials. Over any nonzero ring, the $n$-th cyclotomic polynomial has degree $\varphi(n)$.

The totient function is a multiplicative arithmetic function, and the divisor sum identity expresses that its Dirichlet convolution with the constant function $1$ is the identity function $n \mapsto n$.

In Mathlib

Mathlib defines the function on all natural numbers: $\varphi(n)$ is the number of natural numbers $a$ with $a < n$ that are coprime to $n$. For $n \ge 1$ this agrees with the count over $1, \dots, n$ by the endpoint argument above. At $n = 0$ the range is empty, so $\varphi(0) = 0$, and $0$ is the only number at which $\varphi$ vanishes. With this convention multiplicativity, the bound $\varphi(n) \le n$, the divisor sum (Mathlib's finite set of divisors of $0$ is defined to be empty, so the sum is $0$) and Euler's theorem hold for all natural numbers without excluding $0$. The product formula is stated as an equality of rational numbers, and it also holds at $n = 0$, where both sides are $0$. The count of units of $\mathbb{Z}/n\mathbb{Z}$ assumes $n \neq 0$, since the integers modulo $0$ are the integers themselves.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibNat.totient

Uses 4 · Used by 3

Statement usesNatural number · Greatest common divisor

Proof usesChinese remainder theorem · $\Z/n\Z$ and its invertible elements

Used byEuler’s Generalization of Fermat’s Little Theorem · Dirichlet’s Theorem · Primitive complex roots of unity

TheoremLucas-Lehmer primality test #

The Lucas-Lehmer primality test decides whether a Mersenne number $2^p - 1$ is prime by iterating the map $x \mapsto x^2 - 2$ modulo that number. It needs only $p - 2$ squarings of numbers smaller than $2^p - 1$, far fewer operations than trial division, so that primality is far cheaper to decide for Mersenne numbers than for general numbers of the same size. Mersenne primes are also of independent interest: by the perfect number theorem they correspond to the even perfect numbers.

Statement

For a natural number $p$, the Mersenne number is $M_p = 2^p - 1$. The Lucas-Lehmer sequence of integers is defined by

\[s_0 = 4, \qquad s_{i+1} = s_i^2 - 2,\]

so that its first terms are $4, 14, 194, 37634, \dots$ For $p \ge 2$, the test with exponent $p$ succeeds when $s_{p-2} \equiv 0 \pmod{M_p}$, that is, when $M_p$ divides $s_{p-2}$ (Mathlib runs the recurrence directly modulo $M_p$; see In Mathlib). The theorem has two directions.

Sufficiency. If the test succeeds for an exponent $p \ge 2$, then $M_p$ is prime.
Necessity. If $p \ge 3$ and $M_p$ is prime, then the test succeeds for $p$.

Together they say that for $p \ge 3$, $M_p$ is prime if and only if $M_p$ divides $s_{p-2}$. In practice only prime exponents are tested, because $M_p$ can be prime only when $p$ is prime.

Examples

For $p = 3, 5, 7, 13$ the residues of $s_{p-2}$ modulo $7, 31, 127, 8191$ are all $0$, so these four Mersenne numbers are prime. For $p = 5$ the residues of $s_0, s_1, s_2, s_3$ modulo $31$ are $4, 14, 8, 0$.
For $p = 11$ the residue of $s_9$ modulo $2047$ is $1736$, so $M_{11}$ is composite even though $11$ is prime; indeed $2047 = 23 \cdot 89$.
For $p = 2$ the test fails although $M_2 = 3$ is prime: $s_0 = 4 \equiv 1 \pmod 3$. This is why the necessity direction requires $p \ge 3$.

The reduction modulo $M_p$ is cheap in binary, because every natural number $k$ is congruent modulo $2^n - 1$ to the sum of its quotient and remainder on division by $2^n$, so reducing amounts to shifting and adding.

Proof

Both directions work in the ring $X_q = (\mathbb{Z}/q\mathbb{Z})[\sqrt 3]$, whose elements are pairs $a + b\sqrt 3$ with $a, b$ integers modulo $q$, multiplied using $\sqrt 3^{\,2} = 3$. Put $\omega = 2 + \sqrt 3$ and $\bar\omega = 2 - \sqrt 3$; then $\omega\bar\omega = 1$, and induction on $i$ shows that $s_i = \omega^{2^i} + \bar\omega^{2^i}$ in $X_q$ for every $i$.

Sufficiency. Suppose the test succeeds but $M_p$ is composite, and let $q$ be its smallest prime factor. Then $q^2 \le M_p$, the statement that the smallest prime factor of a positive number that is not prime has square at most that number. Since $q$ divides $M_p$, which divides $s_{p-2}$, the closed form gives $\omega^{2^{p-2}} + \bar\omega^{2^{p-2}} = 0$ in $X_q$; multiplying by $\omega^{2^{p-2}}$ yields $\omega^{2^{p-1}} = -1$, hence $\omega^{2^p} = 1$. As $M_p$ is odd, $q > 2$ and $-1 \ne 1$ in $X_q$, so $\omega$ has order exactly $2^p$ in the group of units of $X_q$ (see order of an element). But the order of an element of a finite group is at most the number of its elements, and for $q > 1$ the ring $X_q$ has fewer than $q^2$ units, since it has $q^2$ elements and $0$ is not a unit. Hence $2^p < q^2 \le M_p = 2^p - 1$, a contradiction.

Necessity. Let $q = M_p$ be prime with $p \ge 3$. Then $2$ is a square modulo $M_p$, because $M_p \equiv 7 \pmod 8$, and, since $p$ is prime (because $M_p$ is) and $p \ge 3$, hence odd, $3$ is not a square modulo $M_p$, by quadratic reciprocity together with $M_p \equiv 3 \pmod 4$ and $M_p \equiv 1 \pmod 3$. The ring $X_q$ has characteristic $q$, and for an odd prime $q$ modulo which $3$ is not a square, $(1 + \sqrt 3)^q = 1 - \sqrt 3$ in $X_q$, since raising to the $q$-th power fixes $\mathbb{Z}/q\mathbb{Z}$ and sends $\sqrt 3$ to $\sqrt 3 \cdot 3^{(q-1)/2} = -\sqrt 3$. From $(1 + \sqrt 3)^2 = 2\omega$ and the fact that $2$ is a square one obtains $\omega^{(q+1)/2} = -1$. Here $(q+1)/2 = 2^{p-1}$, and multiplying $\omega^{2^{p-1}} = -1$ by $\bar\omega^{2^{p-2}}$ gives $\omega^{2^{p-2}} + \bar\omega^{2^{p-2}} = 0$, that is, $s_{p-2} \equiv 0 \pmod{M_p}$.

Lucas's primality criterion shows that $n$ is prime when some $a$ satisfies $a^{n-1} \equiv 1 \pmod n$ but $a^{(n-1)/r} \not\equiv 1 \pmod n$ for every prime $r$ dividing $n - 1$; it suits numbers $n$ for which $n - 1$ is easy to factor, while the Lucas-Lehmer test suits numbers for which $n + 1$ is a power of $2$.
Pépin's test plays the same role for Fermat numbers $F_n = 2^{2^n} + 1$: if $3^{(F_n - 1)/2} \equiv -1 \pmod{F_n}$, then $F_n$ is prime.

In Mathlib

Mathlib states the two directions as separate theorems rather than as one equivalence. The sufficiency direction assumes only $p > 1$, not that $p$ is prime, and the necessity direction assumes $p \ge 3$; the example $p = 2$ shows that this bound cannot be lowered. The test itself is phrased as the vanishing of the recurrence computed directly in the integers modulo $M_p$, and for $p \ge 2$ that computation gives the reduction of $s_i$ modulo $M_p$, so it agrees with the divisibility above. The auxiliary ring $X_q$ is built by hand as pairs of residues modulo $q$ with the multiplication of $a + b\sqrt 3$, rather than as a quotient of a polynomial ring, and the sufficiency proof never needs it to be a field. Mathlib also includes an automatic procedure that evaluates the test for a given numeral exponent, so the primality of a specific Mersenne number can be proved by computation inside the system.

Written for Trough, under CC BY-SA 4.0.

Sources

Mathliblucas_lehmer_sufficiency

Uses 8

Statement usesPrime numbers · Integer · Congruence in $\Z$

Proof usesRing · Group · Order of an element · Characteristic p · Quadratic reciprocity

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.

Divisibility in integral domains

StructureIrreducible element#

Definition

Examples

Irreducible and prime elements

Properties

Related concepts

In Mathlib

Sources

DefinitionCoprime element#

Definition

Examples

Properties

Relation to greatest common divisors

Coprime ideals

In Mathlib

Sources

ClassUnique factorisation domain#

Definition

Examples

Properties

Related concepts

In Mathlib

Sources

AbbreviationGreatest common divisor#

Definition

Examples

Properties

Bézout's identity

Existence

In Mathlib

Sources

AbbreviationLeast common multiple#

Definition

Examples

Properties

Ideals and existence

Related concepts

In Mathlib

Sources

ClassPrincipal ideal domain#

Definition

Examples

Properties

Modules over a principal ideal domain

Related concepts

In Mathlib

Sources

ClassEuclidean domain#

Definition

Examples

Properties

Related concepts

In Mathlib

Sources

DefinitionEuclid's' algorithm#

Definition

Examples

Properties

Generalizations

In Mathlib

Sources

DefinitionEuler's totient function (\(\varphi\))#

Definition

Examples

Properties

Proofs of the main formulas

Applications

Related concepts

In Mathlib

Sources

TheoremLucas-Lehmer primality test#

Statement

Examples

Proof

Related concepts

In Mathlib

Sources

StructureIrreducible element #

DefinitionCoprime element #

ClassUnique factorisation domain #

AbbreviationGreatest common divisor #

AbbreviationLeast common multiple #

ClassPrincipal ideal domain #

ClassEuclidean domain #

DefinitionEuclid's' algorithm #

TheoremLucas-Lehmer primality test #