How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 20 results · all verified · 16 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Divisibility, Greatest Common Divisors and Bézout's Identity

1 · Prerequisites

2 · Summary

Objective. This page opens the number theory track, and it is built entirely on $Z$ as the library constructed it: the ordered commutative ring of The integers form a commutative ring and The integers form a totally ordered ring, with the embedding $ι : N \to Z$ of The naturals embed in the integers and the division algorithm Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ . What is developed here is the divisibility relation and everything that follows from Bézout's identity: greatest common divisors, the Euclidean algorithm and its extended form, coprime integers, least common multiples, and the identification of the subgroups of $(Z, +)$ with the sets of multiples. Primes, Euclid's lemma and unique factorisation are not proved here; they belong to a later page, and no argument below assumes them.

Absolute value on $Z$ , minted here. The library's other absolute value, Absolute value in an ordered field, is stated for an ordered field, and $Z$ is not one, so it does not apply. The absolute value $∣ a ∣$ of an integer therefore defines $∣ a ∣$ for an integer directly, by the case split the total order of $Z$ makes legitimate, and Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ proves the six facts recorded here for later use: positivity, vanishing exactly at $0$ , invariance under negation, multiplicativity, the bound $- ∣ a ∣ \leq a \leq ∣ a ∣$ , and the characterisation of $∣ a ∣ \leq c$ by $- c \leq a \leq c$ . The Remarks of The absolute value $∣ a ∣$ of an integer record that this agrees with Absolute value in an ordered field along the embedding of $Z$ in $Q$ , and nothing on this page depends on that observation. The absolute value is load-bearing rather than convenient: Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ is stated for a positive divisor, so every use of it below first replaces a divisor $b$ by $∣ b ∣$ .

Divisibility, which the library already had. Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ introduces the relation " $b$ divides $a$ " inside its own Statement, for use on its own page, and its Remarks leave the systematic theory to a later page, which "must record that its general divisibility in a ring restricts on $Z$ to the relation defined here, rather than introduce a second notion silently". This is that page: Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ states the same relation, quotes the source, and adds the three boundary values that a page over a ring containing $0$ has to state — $d ∣ 0$ for every $d$ including $0$ , $0 ∣ a$ only for $a = 0$ , and $1 ∣ a$ and $a ∣ a$ always. It is a dictionary item, not new vocabulary. Division with remainder for any nonzero divisor: for $a \in Z$ and $b \neq 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < ∣ b ∣$ then discharges the other promise made in those Remarks, extending division with remainder to every nonzero divisor with $0 \leq r < ∣ b ∣$ , which is possible here precisely because the absolute value has just arrived.

The arithmetic of the relation. Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ proves that divisibility is reflexive, transitive and linear, the linearity clause being the step used by almost every later proof. If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ supplies the one place where divisibility constrains size — $d ∣ a$ with $a \neq 0$ forces $∣ d ∣ \leq ∣ a ∣$ — and it is what makes the set of divisors of a nonzero integer bounded above. $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ identifies the units: $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ , obtained from the published The invertible elements of a monoid form a group under the restricted operation. Associates in $Z$ : integers each of which divides the other and For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$ then show that divisibility cannot distinguish $a$ from $- a$ and nothing more: mutual divisibility, differing by a unit and having equal absolute value are the same condition, and the classes are the pairs ${a, - a}$ .

A greatest element, which well-ordering does not give. The definition of $\gcd$ needs a greatest element of a set of integers bounded above, whereas The well-ordering principle gives a least element of a set of naturals. A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element bridges the two, by reflecting the set through an upper bound into $N$ ; it is general infrastructure, homed here because this is the first page that needs it.

Greatest common divisors, and the convention at $(0, 0)$ . Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ defines $\gcd (a, b)$ as the greatest common divisor, discharging in the definition itself the obligation that one exists: the common divisors are nonempty because $1$ divides everything and bounded above by If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ , so A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element applies. At $(0, 0)$ there is no greatest element at all, and the value is fixed by the convention $\gcd (0, 0) = 0$ , argued where it is made rather than in a footnote: $0$ is greatest in the divisibility ordering, and it is the only value under which $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ holds at $c = 0$ . The companion page carries the witness that makes the convention necessary rather than decorative. $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ then records symmetry, invariance under signs, and the values at $(a, 0)$ , $(a, 1)$ and $(a, a)$ , each checked at $0$ .

Bézout's identity and its corollary. Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution proves that for $a, b$ not both zero the least positive element of ${a x + b y}$ is $\gcd (a, b)$ , by well-ordering and the division algorithm; the last step, that every common divisor is below the gcd and not merely divides it, is where If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ is needed. Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well converts the definition into the form later pages should cite: $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d$ is a common divisor, and every common divisor divides $d$ — a characterisation that, unlike the maximum, holds at $(0, 0)$ too.

The algorithm. If $a = q b + r$ then $a, b$ and $b, r$ have exactly the same common divisors, so $\gcd (a, b) = \gcd (b, r)$ is the whole content of the Euclidean algorithm: $a = q b + r$ makes $a, b$ and $b, r$ have literally the same common divisors, with no inequality on $r$ assumed. The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ turns that into a terminating procedure, defining the remainder descent by The recursion theorem rather than by an informal "iterate", proving termination from the $0 \leq r < b$ clause of the division algorithm, and identifying the last nonzero remainder as the gcd. The extended Euclidean algorithm: the same descent produces integers $x, y$ with $a x + b y = \gcd (a, b)$ , so Bézout coefficients are computed and not merely shown to exist runs the same recursion carrying two coefficient pairs alongside the remainders, so that Bézout coefficients are computed rather than merely shown to exist.

Coprimality. Coprime integers: $\gcd (a, b) = 1$ is $\gcd (a, b) = 1$ , with its three boundary pairs stated; $a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$ gives the usable form, solvability of $a x + b y = 1$ ; and If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ is the lemma that carries the weight, that $\gcd (a, b) = 1$ and $a ∣ b c$ force $a ∣ c$ . It is proved here, from Bézout and with no primality whatever, because primality is only a way of guaranteeing the coprimality it actually uses. $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all integers $a, b, c$ , the identity holding at $c = 0$ and at $(a, b) = (0, 0)$ as well and If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime complete the arithmetic: $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ at every triple, and $a / d$ , $b / d$ are coprime when $d = \gcd (a, b)$ is nonzero.

Least common multiples. Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ defines $lcm (a, b)$ as the least positive common multiple when both arguments are nonzero, and as $0$ otherwise — where $0$ is not a free choice but the only common multiple there is. Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ proves the two facts that matter: every common multiple is a multiple of the lcm, and $\gcd (a, b) lcm (a, b) = ∣ a b ∣$ . The absolute value is not decorative, and the companion page refutes the version without it.

The seam with the group theory. Every subgroup of $(Z, +)$ is $⟨ n ⟩ = n Z$ for exactly one natural number $n$ classifies the subgroups of $(Z, +)$ : each is $n Z = ⟨ n ⟩$ for exactly one natural $n$ . The published example on the examples companion of Binary Operations, Monoids, Groups and Subgroups gives that classification for some such $n$ , but examples pages are leaves in this library's reading order, so nothing here may rest on it — which is why that companion is deliberately absent from the Prerequisites above, while the spine page it accompanies is present. The classification is therefore re-proved here on a spine where later pages can cite it, and re-proved in the stronger form the uses need: its Remarks set out exactly how the two statements differ. $a Z + b Z = \gcd (a, b) Z$ and $a Z \cap b Z = lcm (a, b) Z$ ; equivalently, in $(Z, +)$ the subgroup generated by ${a, b}$ is $⟨ \gcd (a, b) ⟩$ and $⟨ a ⟩ \cap ⟨ b ⟩ = ⟨ lcm (a, b) ⟩$ is then the item that joins the two halves of the page: $a Z + b Z = \gcd (a, b) Z$ and $a Z \cap b Z = lcm (a, b) Z$ . Both inclusions come from Bézout and divisibility alone; the classification is used for exactly one thing, the uniqueness of the nonnegative generator, which is what lets these be read as identifications of subgroups rather than coincidences between sets.

What is deliberately absent. No primes, no Euclid's lemma for a prime divisor, no unique factorisation: those rest on this page and are developed after it. No greatest common divisor of a list longer than a pair, since nothing here needs one. No bound on the number of divisions the Euclidean algorithm performs — the companion page computes the count for one family and proves no worst-case theorem. Twenty-six items make up this page: six definitions, twelve lemmas, four theorems and four corollaries, ten of them marked as landmarks in the flowchart above.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

The absolute value $∣ a ∣$ of an integer

Definition

Let $a \in Z$ (The integers as equivalence classes of pairs of naturals). The absolute value of $a$ is

$∣ a ∣ : = {\begin{cases} a & if a \geq 0, \\ - a & if a < 0, \end{cases}$

where $\leq$ is the order of Order on the integers and $- a$ is the additive inverse supplied by The integers form a commutative ring for the operations of Arithmetic on the integers.

Why the two clauses define a function. The order on $Z$ is total and antisymmetric (The integers form a totally ordered ring), so for each $a$ exactly one of $a \geq 0$ and $a < 0$ holds: totality gives at least one of $0 \leq a$ and $a \leq 0$ , and if both hold then $a = 0$ by antisymmetry, in which case $a \geq 0$ and $a < 0$ fails, since $a < 0$ means $a \leq 0$ together with $a \neq 0$ . The two clauses therefore never both apply and never both fail, and $- a$ is a single element of $Z$ because additive inverses are unique in a commutative ring: if $a + u = 0$ and $a + v = 0$ then $u = u + 0 = u + (a + v) = (u + a) + v = 0 + v = v$ .

At the boundary, $∣ 0 ∣ = 0$ by the first clause, and the second clause also gives $- a$ whenever $a \leq 0$ : for $a < 0$ that is the definition, and for $a = 0$ both readings give $0$ .

Remarks

This is not a second notion of absolute value. The library's other absolute value, Absolute value in an ordered field, is stated for an ordered field. The structure the construction of $Z$ supplies is that of a totally ordered commutative ring (The integers form a commutative ring, The integers form a totally ordered ring), and multiplicative inverses are no part of it, so Absolute value in an ordered field does not apply here and the definition above is a new object rather than a redefinition of an existing one. (That $Z$ is genuinely not a field, rather than merely not presented as one, is $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ below: its only invertible elements are $1$ and $- 1$ .) A general form for an ordered ring would cover both cases at once, but the definition of an ordered ring comes much later in the reading order than this page, so it is not available to reach for.
The two agree along the embedding of $Z$ in $Q$ . Write $j : Z \to Q$ for the injective, order-preserving and arithmetic-preserving map of The integers embed in the rationals. Then $j (∣ a ∣)$ is the absolute value of $j (a)$ in the sense of Absolute value in an ordered field, the check being the same case split: $j$ preserves the order and reflects it (if $j (a) \leq j (b)$ but not $a \leq b$ , then $b \leq a$ by totality, so $j (b) \leq j (a)$ , whence $j (a) = j (b)$ and $a = b$ by injectivity), so $a \geq 0$ exactly when $j (a) \geq 0$ , and $j (- a) = - j (a)$ because $j$ preserves addition. Nothing on this page rests on this observation; it is recorded so that a reader meeting $∣ \cdot ∣$ twice knows the two notations are consistent, and every result below is proved for $Z$ from the integer definition alone.
Why an absolute value is load-bearing here and not a convenience. The published division algorithm Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ is stated for a positive divisor, so every use of it below must first replace a divisor by a positive integer, and $∣ b ∣$ is what that replacement produces.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$

Statement

Let $a, b, c \in Z$ and let $∣ \cdot ∣$ be as in The absolute value $∣ a ∣$ of an integer. Then

$∣ a ∣ \geq 0$ ;
$∣ a ∣ = 0$ if and only if $a = 0$ ;
$∣ - a ∣ = ∣ a ∣$ ;
$∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ;
$- ∣ a ∣ \leq a \leq ∣ a ∣$ ;
$∣ a ∣ \leq c$ if and only if $- c \leq a \leq c$ .

Facts & Assumptions

Given: Integers $a, b, c$ , and the absolute value of The absolute value $∣ a ∣$ of an integer.

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , multiplication distributes over addition, and every $x$ has an additive inverse $- x$ ; we write $u - v$ for $u + (- v)$ . Its standard consequences are used freely: $- (- x) = x$ , $(- x) y = - (x y)$ , $(- x) (- y) = x y$ , $x \cdot 0 = 0$ and $- 0 = 0$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

The order on $Z$ is total, antisymmetric and transitive, is compatible with addition ( $x \leq y$ implies $x + z \leq y + z$ ), and positives are closed under multiplication ( $0 < x$ and $0 < y$ imply $0 < x y$ ); $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

[L3]

$∣ x ∣ = x$ when $x \geq 0$ , and $∣ x ∣ = - x$ when $x \leq 0$ ; the second clause covers $x = 0$ as well, since $- 0 = 0$ (The absolute value $∣ a ∣$ of an integer).

Proof

technique · cases

1.1

For every $x$ : $0 \leq x$ if and only if $- x \leq 0$ , and $x \leq 0$ if and only if $0 \leq - x$ . Adding $- x$ to $0 \leq x$ gives $- x \leq 0$ , and adding $x$ to $- x \leq 0$ gives back $0 \leq x$ ; the second equivalence is the same computation with $x$ and $- x$ interchanged, using $- (- x) = x$ .

L1L2

1.2

If $0 \leq u$ and $0 \leq v$ then $0 \leq u v$ . If $u = 0$ or $v = 0$ then $u v = 0$ ; otherwise $0 < u$ and $0 < v$ , so $0 < u v$ because positives are closed under multiplication.

L1L2

1.3

By totality, at least one of $0 \leq a$ and $a \leq 0$ holds, and correspondingly $∣ a ∣ = a$ or $∣ a ∣ = - a$ ; this is the case split used throughout, and it is exhaustive.

L2L3cases-exhaustive

1.4

Case $a \geq 0$ : $∣ a ∣ = a \geq 0$ .

assume-case nonnegL3

2.1

Case $a \leq 0$ : $∣ a ∣ = - a$ , and $0 \leq - a$ by step 1.1, so $∣ a ∣ \geq 0$ .

assume-case nonposstep 1.1L3

2.2

If $a = 0$ then $∣ a ∣ = 0$ by the first clause. Conversely, if $∣ a ∣ = 0$ then in the case $a \geq 0$ we get $a = ∣ a ∣ = 0$ , and in the case $a \leq 0$ we get $- a = ∣ a ∣ = 0$ , whence $a = - (- a) = - 0 = 0$ . This is claim 2.

step 1.3L1L3

2.3

Claim 3. If $a \geq 0$ then $- a \leq 0$ by step 1.1, so $∣ - a ∣ = - (- a) = a = ∣ a ∣$ . If $a \leq 0$ then $0 \leq - a$ by step 1.1, so $∣ - a ∣ = - a = ∣ a ∣$ .

step 1.1L1L3

2.4

Claim 4, case $a \geq 0$ and $b \geq 0$ : $a b \geq 0$ by step 1.2, so $∣ a b ∣ = a b = ∣ a ∣ ∣ b ∣$ .

assume-case posposstep 1.2L3

2.5

Claim 4, case $a \geq 0$ and $b \leq 0$ : $0 \leq - b$ by step 1.1, so $0 \leq a (- b) = - (a b)$ by step 1.2, hence $a b \leq 0$ by step 1.1 again; therefore $∣ a b ∣ = - (a b) = a (- b) = ∣ a ∣ ∣ b ∣$ .

assume-case posnegstep 1.1step 1.2L1L3

2.6

Claim 4, case $a \leq 0$ and $b \geq 0$ : the same computation with the factors interchanged, using commutativity of multiplication, gives $∣ a b ∣ = (- a) b = ∣ a ∣ ∣ b ∣$ .

assume-case negposstep 1.1step 1.2L1L3

2.7

Claim 4, case $a \leq 0$ and $b \leq 0$ : $0 \leq - a$ and $0 \leq - b$ by step 1.1, so $0 \leq (- a) (- b) = a b$ by step 1.2, hence $∣ a b ∣ = a b = (- a) (- b) = ∣ a ∣ ∣ b ∣$ .

assume-case negnegstep 1.1step 1.2L1L3

2.8

Claim 5. If $a \geq 0$ then $∣ a ∣ = a$ , so $a \leq ∣ a ∣$ ; and $- ∣ a ∣ = - a \leq 0 \leq a$ by step 1.1, so $- ∣ a ∣ \leq a$ by transitivity. If $a \leq 0$ then $∣ a ∣ = - a$ and $0 \leq - a$ by step 1.1, so $a \leq 0 \leq ∣ a ∣$ by transitivity; and $- ∣ a ∣ = - (- a) = a \leq a$ .

step 1.1step 1.3L1L2L3

2.9

Claim 6, from right to left: suppose $- c \leq a \leq c$ . If $a \geq 0$ then $∣ a ∣ = a \leq c$ . If $a \leq 0$ then $∣ a ∣ = - a$ , and adding $c - a$ to $- c \leq a$ gives $- a \leq c$ , that is $∣ a ∣ \leq c$ .

step 1.3L1L2L3

3.1

Claim 1 holds: $∣ a ∣ \geq 0$ in both cases.

step 1.3step 1.4step 2.1cases

3.2

The four sign combinations of step 2.4 to step 2.7 exhaust the possibilities by totality, so claim 4 holds for all $a, b$ .

step 1.3step 2.4step 2.5step 2.6step 2.7cases

3.3

Claim 6, from left to right: suppose $∣ a ∣ \leq c$ . Then $a \leq ∣ a ∣ \leq c$ by step 2.8 and transitivity. Adding $- c - ∣ a ∣$ to $∣ a ∣ \leq c$ gives $- c \leq - ∣ a ∣$ , and $- ∣ a ∣ \leq a$ by step 2.8, so $- c \leq a$ by transitivity.

step 2.8L1L2

4.1

Every one of the six claims is now established, claim 6 by its two halves.

step 3.1step 2.2step 2.3step 3.2step 2.8step 3.3step 2.9∎

Remarks

Claim 6 is stated with $\leq$ on both sides deliberately, and the strict form follows from it: $∣ a ∣ < c$ holds exactly when $- c < a < c$ . From left to right, $a \leq ∣ a ∣ < c$ and $- c < - ∣ a ∣ \leq a$ by claim 5. From right to left, $- c < a < c$ gives $∣ a ∣ \leq c$ by claim 6, and $∣ a ∣ = c$ is impossible, since $∣ a ∣$ is $a$ or $- a$ and both $a = c$ and $- a = c$ are excluded by the two strict inequalities.
The list does not include the triangle inequality, which is not used anywhere on this page. What the proofs below actually reach for is claim 1, claim 2, claim 4 and the bound $a \leq ∣ a ∣$ of claim 5; claim 3 is used once, in the identification of the associate classes, and claim 6 is recorded for completeness rather than because something later needs it.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$

Definition

Let $d, a \in Z$ (The integers as equivalence classes of pairs of naturals). We say $d$ divides $a$ , and write $d ∣ a$ , when

$a = d q for some q \in Z,$

the product being that of Arithmetic on the integers. We write $d ∤ a$ when this fails. In this situation $d$ is called a divisor, or a factor, of $a$ , and $a$ is called a multiple of $d$ .

This is the relation the library already has, not a second one. The published Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ introduces it in its own Statement, in these words: "We say $b$ divides $a$ , written $b ∣ a$ , when $a = q b$ for some $q \in Z$ ." Since multiplication on $Z$ is commutative (The integers form a commutative ring), $a = q d$ and $a = d q$ are the same condition, so the definition above is that relation verbatim and the two usages agree everywhere. The theorem defined it for use on its own page and left the systematic theory to a later page; this is that page, and this item records the agreement rather than introducing a rival notion.

The remainder test. For $b > 0$ the same Statement records that $b ∣ a$ holds exactly when the remainder $r$ in $a = q b + r$ , $0 \leq r < b$ , is $0$ .

Boundary values. Each is one line from the ring axioms, and each is used below, so all three are recorded here rather than assumed:

$d ∣ 0$ for every integer $d$ , including $d = 0$ , since $0 = d \cdot 0$ ;
$0 ∣ a$ only for $a = 0$ , since $a = 0 \cdot q$ forces $a = 0$ ;
$1 ∣ a$ and $a ∣ a$ for every $a$ , since $a = 1 \cdot a$ and $a = a \cdot 1$ .

Remarks

The remainder test for a negative divisor is Division with remainder for any nonzero divisor: for $a \in Z$ and $b \neq 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < ∣ b ∣$ , proved next: for every $b \neq 0$ , $b ∣ a$ holds exactly when the remainder in $a = q b + r$ , $0 \leq r < ∣ b ∣$ , is $0$ .
$d ∣ a$ says a quotient exists; it says nothing on its own about the size or the sign of $d$ . Signs are irrelevant to it — $2 ∣ - 4$ , $- 2 ∣ 4$ and $- 2 ∣ - 4$ all hold — and that is Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ . The one place where divisibility does constrain size is If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ , and it needs the hypothesis $a \neq 0$ : without it $d ∣ 0$ holds for arbitrarily large $∣ d ∣$ .
Notation. The bar in $d ∣ a$ is a relation symbol read from left to right: the divisor is on the left. The reversed reading is a common slip, and the two directions are genuinely different, since $2 ∣ 4$ holds while $4 ∤ 2$ (by If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ , $4 ∣ 2$ with $2 \neq 0$ would force $4 = ∣ 4 ∣ \leq ∣ 2 ∣ = 2$ ).

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Division with remainder for any nonzero divisor: for $a \in Z$ and $b \neq 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < ∣ b ∣$

Statement

Let $a, b \in Z$ with $b \neq 0$ . Then there is exactly one pair $(q, r)$ of integers with

$a = q b + r, 0 \leq r < ∣ b ∣,$

the absolute value being that of The absolute value $∣ a ∣$ of an integer. Moreover $b ∣ a$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ) holds exactly when $r = 0$ .

Facts & Assumptions

Given: Integers $a$ and $b$ with $b \neq 0$ .

[L1]

For $a \in Z$ and $b^{'} > 0$ there is exactly one pair $(Q, r)$ of integers with $a = Q b^{'} + r$ and $0 \leq r < b^{'}$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L2]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , multiplication distributes over addition, and every $x$ has an additive inverse $- x$ , with $- (- x) = x$ and $(- x) (- y) = x y$ (The integers form a commutative ring, Arithmetic on the integers).

[L3]

The order on $Z$ is total, antisymmetric and transitive; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

[L4]

$∣ x ∣ = x$ when $x \geq 0$ and $∣ x ∣ = - x$ when $x \leq 0$ (The absolute value $∣ a ∣$ of an integer); $∣ x ∣ \geq 0$ , and $∣ x ∣ = 0$ exactly when $x = 0$ (Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L5]

$b ∣ a$ means $a = b s$ for some $s \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

Proof

technique · cases

1.1

$0 < ∣ b ∣$ : indeed $∣ b ∣ \geq 0$ , and $∣ b ∣ \neq 0$ because $b \neq 0$ .

L4given

1.2

Case $b > 0$ : put $ε : = 1$ . Then $∣ b ∣ = b$ , so $ε ∣ b ∣ = b$ , and $ε^{2} = 1$ .

assume-case posL2L4

1.3

Case $b < 0$ : put $ε : = - 1$ . Then $∣ b ∣ = - b$ , so $ε ∣ b ∣ = - (- b) = b$ , and $ε^{2} = (- 1) (- 1) = 1$ .

assume-case negL2L4

2.1

Since $b \neq 0$ , totality gives $0 \leq b$ or $b \leq 0$ , hence $b > 0$ or $b < 0$ ; so in either case there is an integer $ε$ with $b = ε ∣ b ∣$ and $ε^{2} = 1$ .

step 1.2step 1.3L3givencases

2.2

By [L1] applied to $a$ and the positive integer $∣ b ∣$ , there is exactly one pair $(Q, r)$ of integers with $a = Q ∣ b ∣ + r$ and $0 \leq r < ∣ b ∣$ .

step 1.1L1

3.1

Existence. Put $q : = ε Q$ . Then $q b = ε Q \cdot ε ∣ b ∣ = ε^{2} Q ∣ b ∣ = Q ∣ b ∣$ , so $a = q b + r$ with $0 \leq r < ∣ b ∣$ .

step 2.1step 2.2L2

3.2

Uniqueness. Suppose $a = q_{1} b + r_{1} = q_{2} b + r_{2}$ with $0 \leq r_{i} < ∣ b ∣$ for $i = 1, 2$ . Since $b = ε ∣ b ∣$ , this reads $a = (ε q_{1}) ∣ b ∣ + r_{1} = (ε q_{2}) ∣ b ∣ + r_{2}$ , two representations of the form required by [L1] for the divisor $∣ b ∣$ ; hence $ε q_{1} = ε q_{2}$ and $r_{1} = r_{2}$ . Multiplying the first equation by $ε$ and using $ε^{2} = 1$ gives $q_{1} = q_{2}$ .

step 2.1step 2.2L1L2

4.1

The remainder test. If $r = 0$ then $a = q b$ , so $b ∣ a$ . Conversely, if $b ∣ a$ , say $a = b s$ , then $a = s b + 0$ and $0 \leq 0 < ∣ b ∣$ by step 1.1, so this is a representation of the required form and uniqueness forces $r = 0$ .

step 1.1step 3.1step 3.2L2L5

5.1

Existence is step 3.1, uniqueness is step 3.2, and the remainder test is step 4.1, which is the full statement.

step 3.1step 3.2step 4.1∎

Remarks

What this discharges. Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ is stated for a positive divisor, and its own Remarks record that "the version for $b \neq 0$ , with $0 \leq r < ∣ b ∣$ , follows once absolute values are in hand". Absolute values on $Z$ arrive on this page (The absolute value $∣ a ∣$ of an integer), so the promise is discharged here.
The remainder is still taken nonnegative, and that is a choice. With $a = - 7$ and $b = - 3$ the statement above gives $- 7 = 3 \cdot (- 3) + 2$ , so $q = 3$ and $r = 2$ , whereas truncating the quotient toward zero would give $q = 2$ and $r = - 1$ , which the constraint $0 \leq r$ excludes. The clause $0 \leq r < ∣ b ∣$ is the one every use below makes, and no other convention is introduced anywhere on this page.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$

Statement

Let $a, b, c, d, x, y \in Z$ and let $∣$ be divisibility (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ). Then

reflexivity: $a ∣ a$ ;
transitivity: $d ∣ a$ and $a ∣ b$ imply $d ∣ b$ ;
linearity: $d ∣ a$ and $d ∣ b$ imply $d ∣ a x + b y$ ; in particular $d ∣ a + b$ and $d ∣ a - b$ ;
$d ∣ a$ implies $d ∣ a c$ ;
$d ∣ a$ implies $- d ∣ a$ and $d ∣ - a$ .

Consequently the four statements $d ∣ a$ , $- d ∣ a$ , $d ∣ - a$ and $- d ∣ - a$ are equivalent.

Facts & Assumptions

Given: Integers $a, b, c, d, x, y$ .

[L1]

$d ∣ a$ means $a = d q$ for some $q \in Z$ ; $a = a \cdot 1$ exhibits $a ∣ a$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L2]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , multiplication distributes over addition, and every $x$ has an additive inverse $- x$ , with $- (- x) = x$ , $(- x) y = - (x y)$ and $(- x) (- y) = x y$ ; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers).

Proof

technique · direct

1.1

Reflexivity: $a = a \cdot 1$ , so $a ∣ a$ .

L1L2

1.2

Transitivity: suppose $a = d m$ and $b = a n$ . Then $b = (d m) n = d (m n)$ by associativity, so $d ∣ b$ .

L1L2

1.3

Linearity: suppose $a = d m$ and $b = d n$ . Then $a x + b y = (d m) x + (d n) y = d (m x + n y)$ by associativity, commutativity and distributivity, so $d ∣ a x + b y$ .

L1L2

1.4

Clause 4: suppose $a = d m$ . Then $a c = (d m) c = d (m c)$ , so $d ∣ a c$ .

L1L2

1.5

Clause 5: suppose $a = d m$ . Then $a = (- d) (- m)$ , so $- d ∣ a$ ; and $- a = - (d m) = d (- m)$ , so $d ∣ - a$ .

L1L2

2.1

The two special cases in clause 3: taking $x = y = 1$ gives $d ∣ a + b$ , and taking $x = 1$ , $y = - 1$ gives $d ∣ a \cdot 1 + b \cdot (- 1) = a - b$ .

step 1.3L2

2.2

The four equivalent forms: clause 5 gives $d ∣ a \Rightarrow - d ∣ a$ and $d ∣ a \Rightarrow d ∣ - a$ ; applying each to $- d$ in place of $d$ , or to $- a$ in place of $a$ , and using $- (- x) = x$ , gives the reverse implications, so all four statements are equivalent.

step 1.5L2

3.1

Clauses 1 to 5 and the two consequences are established.

step 1.1step 1.2step 1.3step 1.4step 1.5step 2.1step 2.2∎

Remarks

Linearity is the workhorse of the whole page. Every later argument that a common divisor of $a$ and $b$ divides some combination of them — Bézout's identity, the Euclidean step, the coprimality criterion — is clause 3 applied once.
Divisibility ignores signs, and that is why $\gcd$ can be normalised. Clause 5 says the divisors of $a$ and of $- a$ are the same set, so $d ∣ a$ holds exactly when $d ∣ ∣ a ∣$ , whichever of the two values $∣ a ∣$ takes (The absolute value $∣ a ∣$ of an integer). That is the observation behind $\gcd (a, b) = \gcd (∣ a ∣, ∣ b ∣)$ in $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$

Statement

Let $a, d \in Z$ with $d ∣ a$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ) and $a \neq 0$ . Then $d \neq 0$ and

$∣ d ∣ \leq ∣ a ∣ .$

Consequently, for $a \neq 0$ the set ${d \in Z : d ∣ a}$ of divisors of $a$ is bounded above by $∣ a ∣$ : every divisor $d$ of $a$ satisfies $d \leq ∣ a ∣$ .

Facts & Assumptions

Given: Integers $a$ and $d$ with $a = d q$ for some $q \in Z$ and $a \neq 0$ ; and the embedding $ι : N \to Z$ , $ι (k) = [(k, 0)]$ , of The naturals embed in the integers.

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , $x \cdot 0 = 0$ , multiplication distributes over addition, and every $x$ has an additive inverse $- x$ ; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

The order on $Z$ is total, antisymmetric and transitive, is compatible with addition, and positives are closed under multiplication; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

[L3]

$ι$ is injective, preserves addition, multiplication and order, and its image is exactly the set of nonnegative integers; $ι (0) = 0$ and $ι (1) = 1$ (The naturals embed in the integers, The integers as equivalence classes of pairs of naturals).

[L4]

On $N$ : $m < n$ if and only if $σ (m) \leq n$ (Discreteness: $σ (n)$ is the immediate successor); $1 = σ (0)$ (The natural numbers $N$ (von Neumann)); and $0 \leq k$ for every $k$ , since $0 + k = k$ (Order on the natural numbers).

[L5]

$∣ x ∣ \geq 0$ ; $∣ x ∣ = 0$ exactly when $x = 0$ ; $∣ x y ∣ = ∣ x ∣ ∣ y ∣$ ; and $x \leq ∣ x ∣$ (Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ , The absolute value $∣ a ∣$ of an integer).

[L6]

$d ∣ a$ means $a = d q$ for some $q \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

Proof

technique · direct

1.1

Write $a = d q$ . If $d = 0$ then $a = 0 \cdot q = 0$ , and if $q = 0$ then $a = d \cdot 0 = 0$ ; both contradict $a \neq 0$ , so $d \neq 0$ and $q \neq 0$ .

givenL1L6

1.2

If $0 \leq u$ and $0 \leq v$ then $0 \leq u v$ : if $u = 0$ or $v = 0$ then $u v = 0$ , and otherwise $0 < u$ and $0 < v$ , so $0 < u v$ because positives are closed under multiplication.

L1L2

1.3

Discreteness of $Z$ : if $0 < x$ then $1 \leq x$ . Indeed $x \geq 0$ , so $x = ι (k)$ for some $k \in N$ ; $k \neq 0$ because $ι (0) = 0 \neq x$ ; hence $0 < k$ in $N$ , so $1 = σ (0) \leq k$ , and applying $ι$ , which preserves the order, gives $1 = ι (1) \leq ι (k) = x$ .

L2L3L4

2.1

$∣ a ∣ = ∣ d ∣ ∣ q ∣$ , and $∣ q ∣ > 0$ because $∣ q ∣ \geq 0$ and $∣ q ∣ \neq 0$ , the latter since $q \neq 0$ .

step 1.1L5

3.1

Hence $1 \leq ∣ q ∣$ , so $0 \leq ∣ q ∣ - 1$ by compatibility of the order with addition.

step 1.3step 2.1L2

4.1

Since $∣ d ∣ \geq 0$ and $0 \leq ∣ q ∣ - 1$ , the product $∣ d ∣ (∣ q ∣ - 1)$ is nonnegative, and it equals $∣ d ∣ ∣ q ∣ - ∣ d ∣ = ∣ a ∣ - ∣ d ∣$ by distributivity; adding $∣ d ∣$ gives $∣ d ∣ \leq ∣ a ∣$ .

step 1.2step 2.1step 3.1L1L2L5

5.1

Finally, every divisor $d$ of $a$ satisfies $d \leq ∣ d ∣$ and $∣ d ∣ \leq ∣ a ∣$ , hence $d \leq ∣ a ∣$ by transitivity: $∣ a ∣$ is an upper bound for the set of divisors of $a$ .

step 4.1L2L5∎

Remarks

There is no excluded case at $d = 0$ . The hypothesis is $a \neq 0$ , and the conclusion derives $d \neq 0$ rather than assuming it: $0 ∣ a$ forces $a = 0$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ), so a zero divisor simply cannot occur under this hypothesis. The statement is therefore not vacuous anywhere, and it is not silently excluding a case.
The hypothesis $a \neq 0$ cannot be dropped. Every integer divides $0$ , so the divisors of $0$ are all of $Z$ and are bounded neither above nor below. This is exactly why the greatest common divisor of $(0, 0)$ has to be fixed by a convention rather than by a maximum (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

$(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$

Statement

$(Z, \cdot, 1)$ , with the multiplication of Arithmetic on the integers, is a commutative monoid (Semigroup and monoid). Its group of units (Left inverse, right inverse, and invertible element of a monoid, The invertible elements of a monoid form a group under the restricted operation) is

$Z^{\times} = {1, - 1},$

and these are two distinct elements. Equivalently, for $u \in Z$ the condition $u ∣ 1$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ) holds exactly when $u = 1$ or $u = - 1$ .

Facts & Assumptions

Given: $Z$ with the operations of Arithmetic on the integers, and the embedding $ι : N \to Z$ , $ι (k) = [(k, 0)]$ , of The naturals embed in the integers.

[L1]

$Z$ is a commutative ring: multiplication is a function $Z \times Z \to Z$ and is associative and commutative, $x \cdot 1 = x$ , and every $x$ has an additive inverse $- x$ , with $- (- x) = x$ and $(- x) (- y) = x y$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

The order on $Z$ is total, antisymmetric and transitive, and positives are closed under multiplication; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

[L3]

A binary operation on a set $S$ is a function $S \times S \to S$ ; a monoid is a set with an associative binary operation and a two-sided identity, and it is commutative when the operation is (Binary operation on a set; associativity, commutativity, and a subset closed under the operation, Left identity, right identity, and two-sided identity for a binary operation, Semigroup and monoid).

[L4]

In a monoid $M$ , $u$ is a unit when it has a two-sided inverse, and $M^{\times}$ denotes the set of units; $M^{\times}$ is a group under the restricted operation (Left inverse, right inverse, and invertible element of a monoid, The invertible elements of a monoid form a group under the restricted operation, Group and abelian group).

[L5]

$u ∣ a$ means $a = u v$ for some $v \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L6]

If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

[L7]

$∣ x ∣ = x$ when $x \geq 0$ and $∣ x ∣ = - x$ when $x \leq 0$ (The absolute value $∣ a ∣$ of an integer); $∣ x ∣ \geq 0$ and $∣ x ∣ = 0$ exactly when $x = 0$ (Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L8]

[L9]

On $N$ : $m < n$ if and only if $σ (m) \leq n$ (Discreteness: $σ (n)$ is the immediate successor); $0 = \emptyset$ , $1 = σ (0) = {0}$ and $2 = σ (1) = {0, 1}$ , so $1 \neq 0$ and $2 \neq 0$ (The natural numbers $N$ (von Neumann)); and $0 \leq k$ for every $k$ (Order on the natural numbers).

Proof

technique · direct

1.1

Multiplication on $Z$ is a function $Z \times Z \to Z$ , hence a binary operation, and it is associative and commutative; $1$ is a two-sided identity, since $x \cdot 1 = x$ and, by commutativity, $1 \cdot x = x$ . So $(Z, \cdot, 1)$ is a commutative monoid.

L1L3

1.2

For $u \in Z$ , being a unit of this monoid means $u v = 1$ for some $v$ , the two equations $u v = 1$ and $v u = 1$ being the same by commutativity; and $u v = 1$ for some $v$ is precisely $u ∣ 1$ . So $Z^{\times} = {u : u ∣ 1}$ .

L1L4L5

1.3

Both $1$ and $- 1$ lie in $Z^{\times}$ : $1 \cdot 1 = 1$ and $(- 1) (- 1) = 1 \cdot 1 = 1$ .

L1L4

1.4

$0 \leq 1$ , since $1 = ι (1)$ lies in the image of $ι$ , which is the set of nonnegative integers; hence $∣ 1 ∣ = 1$ . Also $1 \neq 0$ , since $ι$ is injective and $1 \neq 0$ in $N$ .

L7L8

1.5

L2L8L9

1.6

$1 \neq - 1$ : otherwise $1 + 1 = 1 + (- 1) = 0$ , whereas $1 + 1 = ι (1) + ι (1) = ι (1 + 1) = ι (2)$ and $ι (2) \neq ι (0) = 0$ because $ι$ is injective and $2 \neq 0$ in $N$ .

L1L8L9

2.1

Let $u ∣ 1$ . Since $1 \neq 0$ , [L6] gives $u \neq 0$ and $∣ u ∣ \leq ∣ 1 ∣ = 1$ .

step 1.4L6

3.1

Also $∣ u ∣ \geq 0$ and $∣ u ∣ \neq 0$ , so $0 < ∣ u ∣$ , whence $1 \leq ∣ u ∣$ ; with step 2.1 and antisymmetry this gives $∣ u ∣ = 1$ .

step 1.5step 2.1L2L7

4.1

From $∣ u ∣ = 1$ : if $u \geq 0$ then $u = ∣ u ∣ = 1$ , and if $u \leq 0$ then $- u = ∣ u ∣ = 1$ , so $u = - (- u) = - 1$ . By totality one of the two holds, so $u = 1$ or $u = - 1$ .

step 3.1L1L2L7

5.1

Combining, $Z^{\times} = {u : u ∣ 1} = {1, - 1}$ , a two-element set, and by [L4] it is a group under multiplication, with identity $1$ and with each of its elements its own inverse.

step 1.2step 1.3step 4.1step 1.6L4∎

Remarks

Why this is proved here and not cited. The published example $(Z, +)$ is an abelian group, $(Z, \cdot)$ is a commutative monoid that is not a group, and its group of units is ${1, - 1}$ records the same fact, $Z^{\times} = {1, - 1}$ , but it lives on an examples page, and pages of that kind are leaves in the library's reading order: nothing later may depend on them. The statement is therefore re-established here, on a spine, so that later pages have a citable home for it. The two agree; neither rests on the other.
The proof is an application of the divisor bound, not a computation. What makes ${1, - 1}$ the whole answer is that $u ∣ 1$ forces $∣ u ∣ \leq 1$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ) while $u \neq 0$ forces $∣ u ∣ \geq 1$ (discreteness), and antisymmetry closes the gap. Nothing about the decimal shape of an integer is used.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Associates in $Z$ : integers each of which divides the other

Definition

Integers $a$ and $b$ are associates, written $a \sim b$ , when each divides the other (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ):

$a \sim b : ⟺ a ∣ b and b ∣ a .$

As a binary relation in the sense of Equivalence relation, equivalence class, and the quotient set $A / \sim$ this is the subset

$R = {(a, b) \in Z \times Z : a ∣ b and b ∣ a}$

of $Z \times Z$ , and $a \sim b$ abbreviates $(a, b) \in R$ .

Nothing is claimed here beyond the definition. That $R$ is an equivalence relation — reflexive, symmetric and transitive — is a statement about $R$ that has to be proved, and it is proved next, in For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$ , together with the identification of the class of $a$ as ${a, - a}$ . Until then the symbol $\sim$ is notation for membership of $R$ and carries no further content; in particular the language of equivalence classes is not used above.

Remarks

Why the notion is worth naming. Divisibility does not distinguish an integer from its negative (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ), so it is a preorder rather than an order: $2 ∣ - 2$ and $- 2 ∣ 2$ while $2 \neq - 2$ . Associates are exactly the pairs that divisibility cannot tell apart, and naming them is what lets the greatest common divisor be pinned down by a sign convention rather than left ambiguous up to that failure.
The classes have at most two elements, which is special to $Z$ and comes from its group of units being ${1, - 1}$ ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ). The class of $0$ is ${0}$ alone.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$

Statement

Let $a, b \in Z$ . The following are equivalent:

$a ∣ b$ and $b ∣ a$ , that is, $a \sim b$ (Associates in $Z$ : integers each of which divides the other);
$b = u a$ for some unit $u \in Z^{\times} = {1, - 1}$ ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ );
$∣ a ∣ = ∣ b ∣$ (The absolute value $∣ a ∣$ of an integer).

Moreover $\sim$ is an equivalence relation on $Z$ (Equivalence relation, equivalence class, and the quotient set $A / \sim$ ), and the class of $a$ is

$[a] = {a, - a},$

which is ${0}$ when $a = 0$ and has exactly two elements otherwise.

Facts & Assumptions

Given: Integers $a$ and $b$ , and the relation $\sim$ of Associates in $Z$ : integers each of which divides the other.

[L1]

$Z$ is a commutative ring, with $- (- x) = x$ , $(- x) y = - (x y)$ , $x \cdot 1 = x$ and $x \cdot 0 = 0$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

The order on $Z$ is total, antisymmetric and transitive, is compatible with addition ( $x \leq y$ implies $x + z \leq y + z$ ), and positives are closed under multiplication ( $0 < x$ and $0 < y$ imply $0 < x y$ ) (The integers form a totally ordered ring, Order on the integers).

[L3]

$d ∣ a$ means $a = d q$ for some $q$ ; $0 ∣ a$ only for $a = 0$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L4]

Divisibility is reflexive and transitive, and $d ∣ a$ implies $d ∣ - a$ and $- d ∣ a$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L5]

[L6]

$Z^{\times} = {1, - 1}$ : an integer $u$ is a unit exactly when $u = 1$ or $u = - 1$ , and $1 \neq - 1$ ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ).

[L7]

$∣ x ∣ = x$ when $x \geq 0$ and $∣ x ∣ = - x$ when $x \leq 0$ (The absolute value $∣ a ∣$ of an integer); $∣ x ∣ \geq 0$ , $∣ x ∣ = 0$ exactly when $x = 0$ , and $∣ x y ∣ = ∣ x ∣ ∣ y ∣$ (Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L8]

A relation is an equivalence relation when it is reflexive, symmetric and transitive, and then the class of $a$ is $[a] = {b : a \sim b}$ (Equivalence relation, equivalence class, and the quotient set $A / \sim$ ).

[L9]

The classes of an equivalence relation are nonempty, cover the set, and are pairwise equal or disjoint (The equivalence classes of an equivalence relation are nonempty, cover $A$ , and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation).

Proof

technique · direct

1.1

Every integer $x$ satisfies $x = ∣ x ∣$ or $x = - ∣ x ∣$ : by totality either $x \geq 0$ , when $∣ x ∣ = x$ , or $x \leq 0$ , when $∣ x ∣ = - x$ and so $x = - (- x) = - ∣ x ∣$ .

L1L2L7

1.2

$1 \neq 0$ , $0 < 1$ , $∣ 1 ∣ = 1$ and $∣ - 1 ∣ = 1$ . Indeed $1 = 0$ would give $- 1 = - 0 = 0 = 1$ , contradicting $1 \neq - 1$ in [L6]. By totality either $0 \leq 1$ or $1 \leq 0$ ; in the second case adding $- 1$ gives $0 \leq - 1$ , and $- 1 \neq 0$ (else $1 = 0$ ), so $0 < - 1$ , hence $0 < (- 1) (- 1) = 1$ , which with $1 \leq 0$ contradicts antisymmetry. So $0 \leq 1$ , and $0 < 1$ since $1 \neq 0$ ; then $∣ 1 ∣ = 1$ , while $0 \leq 1$ gives $- 1 \leq 0$ by compatibility with addition, so $∣ - 1 ∣ = - (- 1) = 1$ .

L1L2L6L7

1.3

Claim 1 implies claim 3. Suppose $a ∣ b$ and $b ∣ a$ . If $a = 0$ then $0 ∣ b$ forces $b = 0$ , so $∣ a ∣ = 0 = ∣ b ∣$ . If $a \neq 0$ , then $b ∣ a$ with $a \neq 0$ gives $b \neq 0$ and $∣ b ∣ \leq ∣ a ∣$ , and $a ∣ b$ with $b \neq 0$ gives $∣ a ∣ \leq ∣ b ∣$ ; antisymmetry gives $∣ a ∣ = ∣ b ∣$ .

L2L3L5L7

1.4

$\sim$ is reflexive, since $a ∣ a$ ; symmetric, since its defining condition is unchanged when $a$ and $b$ are interchanged; and transitive, since $a ∣ b$ , $b ∣ c$ give $a ∣ c$ and $c ∣ b$ , $b ∣ a$ give $c ∣ a$ . So it is an equivalence relation.

L4L8

2.1

Claim 3 implies claim 1. Suppose $∣ a ∣ = ∣ b ∣$ . By step 1.1, $b$ is $∣ b ∣$ or $- ∣ b ∣$ , that is $∣ a ∣$ or $- ∣ a ∣$ ; and, again by step 1.1, $∣ a ∣$ is $a$ or $- a$ . Hence $b = a$ or $b = - a$ . If $b = a$ then $a ∣ b$ and $b ∣ a$ by reflexivity. If $b = - a$ then $a ∣ - a = b$ by [L4]; and $b = - a$ gives $a = - (- a) = - b$ , so $b ∣ - b = a$ , again by [L4].

step 1.1L1L4

2.2

Claim 2 implies claim 3. If $b = u a$ with $u$ a unit then $u = 1$ or $u = - 1$ , so $∣ u ∣ = 1$ by step 1.2, and $∣ b ∣ = ∣ u ∣ ∣ a ∣ = ∣ a ∣$ .

step 1.2L6L7

3.1

Claim 3 implies claim 2. By step 2.1, $∣ a ∣ = ∣ b ∣$ gives $b = a = 1 \cdot a$ or $b = - a = (- 1) a$ , and $1$ and $- 1$ are units.

step 2.1L1L6

4.1

The three claims are equivalent: claim 3 implies claim 1 by step 2.1 and claim 1 implies claim 3 by step 1.3, while claim 3 implies claim 2 by step 3.1 and claim 2 implies claim 3 by step 2.2.

step 2.1step 1.3step 2.2step 3.1

5.1

The class of $a$ is $[a] = {b : a \sim b} = {b : ∣ b ∣ = ∣ a ∣} = {a, - a}$ : the middle equality is the equivalence of claims 1 and 3, and the last holds because $∣ - a ∣ = ∣ a ∣$ by [L7], while conversely $∣ b ∣ = ∣ a ∣$ gives $b = a$ or $b = - a$ by step 2.1. At $a = 0$ this set is ${0}$ , since $- 0 = 0$ ; and for $a \neq 0$ it has exactly two elements, since by totality either $0 < a$ , when adding $- a$ gives $- a < 0 < a$ , or $a < 0$ , when adding $- a$ gives $a < 0 < - a$ ; in both cases $a \neq - a$ .

step 2.1step 4.1L1L2L7L8

6.1

By [L9] the classes ${a, - a}$ are nonempty, cover $Z$ , and any two are equal or disjoint; together with steps 4.1, 1.4 and 5.1 this is the full statement.

step 4.1step 1.4step 5.1L9∎

Remarks

This is the "up to sign" of elementary number theory made precise. Every statement below that fixes a sign — $\gcd (a, b) \geq 0$ , $lcm (a, b) \geq 0$ , the nonnegative generator of a subgroup of $(Z, +)$ — is choosing one representative from a class ${a, - a}$ , and claim 3 is what says the choice is between exactly two candidates.
The equivalence of claims 1 and 2 is the general ring-theoretic statement, and it is the reason associates are defined by mutual divisibility rather than by "differ by a sign": mutual divisibility is the formulation that survives when the unit group is larger than ${1, - 1}$ .

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element

Statement

Let $S \subseteq Z$ be nonempty. Call $b \in Z$ an upper bound for $S$ when $s \leq b$ for every $s \in S$ , and a lower bound when $b \leq s$ for every $s \in S$ ; call $m$ a greatest element of $S$ when $m \in S$ and $s \leq m$ for every $s \in S$ , and a least element when $m \in S$ and $m \leq s$ for every $s \in S$ .

If $S$ has an upper bound, it has a greatest element. If $S$ has a lower bound, it has a least element. In each case the element is unique.

Facts & Assumptions

Given: A nonempty $S \subseteq Z$ , and the embedding $ι : N \to Z$ , $ι (k) = [(k, 0)]$ , of The naturals embed in the integers.

[L1]

$Z$ is a commutative ring: addition is associative and commutative, $x + 0 = x$ , and every $x$ has an additive inverse $- x$ , with $- (- x) = x$ ; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L2]

The order on $Z$ is total, antisymmetric and transitive, and is compatible with addition: $x \leq y$ implies $x + z \leq y + z$ (The integers form a totally ordered ring, Order on the integers).

[L3]

$ι$ is injective, preserves addition, multiplication and order, and its image is exactly the set of nonnegative integers, so every $x \geq 0$ is $ι (k)$ for a unique $k \in N$ (The naturals embed in the integers, The natural numbers $N$ (von Neumann)).

[L4]

Every nonempty subset of $N$ has a least element (The well-ordering principle, Order on the natural numbers).

Proof

technique · direct

1.1

Suppose $b$ is an upper bound for $S$ . For every $s \in S$ we have $s \leq b$ , and adding $- s$ gives $0 \leq b - s$ ; so $b - s$ is nonnegative and therefore equals $ι (k)$ for a unique $k \in N$ .

givenL1L2L3

1.2

Now suppose instead that $c$ is a lower bound for $S$ , and put $S^{'} : = {- s : s \in S}$ , a nonempty subset of $Z$ . For $s \in S$ , adding $- s - c$ to $c \leq s$ gives $- s \leq - c$ , so $- c$ is an upper bound for $S^{'}$ .

givenL1L2

2.1

Put $T : = {k \in N : b - ι (k) \in S}$ . It is nonempty: choosing $s \in S$ and the $k$ of step 1.1 with $ι (k) = b - s$ , we get $b - ι (k) = b - (b - s) = s \in S$ , so $k \in T$ .

step 1.1L1given

3.1

By well-ordering let $k_{0}$ be the least element of $T$ , and put $m : = b - ι (k_{0})$ , so that $m \in S$ .

step 2.1L4choose

4.1

Let $s \in S$ . By step 1.1 there is $k \in N$ with $ι (k) = b - s$ , and then $b - ι (k) = s \in S$ , so $k \in T$ and hence $k_{0} \leq k$ .

step 1.1step 2.1step 3.1L1

5.1

Applying $ι$ , which preserves the order, gives $ι (k_{0}) \leq ι (k) = b - s$ ; adding $s - ι (k_{0})$ to this inequality gives $s \leq b - ι (k_{0}) = m$ .

step 3.1step 4.1L1L2L3

6.1

So $m \in S$ and $s \leq m$ for every $s \in S$ : $m$ is a greatest element of $S$ . If $m^{'}$ were another one, then $m \leq m^{'}$ and $m^{'} \leq m$ , so $m = m^{'}$ by antisymmetry.

step 3.1step 5.1L2

7.1

By the first part $S^{'}$ has a greatest element, which has the form $- ℓ$ with $ℓ \in S$ ; then for every $s \in S$ we have $- s \leq - ℓ$ , and adding $s + ℓ$ gives $ℓ \leq s$ . So $ℓ$ is a least element of $S$ , and it is unique by antisymmetry as in step 6.1.

step 6.1step 1.2L1L2∎

Remarks

Why this has to be proved rather than quoted. The well-ordering principle (The well-ordering principle) gives a least element of a nonempty set of naturals. What the greatest common divisor needs is a greatest element of a set of integers bounded above, and neither the direction nor the ambient set matches. The bridge is the reflection $k \mapsto b - ι (k)$ , which turns "large elements of $S$ below $b$ " into "small naturals".
Both hypotheses are needed. $Z$ itself is nonempty and has no greatest element, and $\emptyset$ is bounded above by every integer and has no greatest element because it has no element at all. The first of these is exactly what makes the common divisors of $(0, 0)$ have no greatest element (The common divisors of $(0, 0)$ are all of $Z$ and have no greatest element in the order of $Z$ , so $\gcd (0, 0)$ cannot be defined as a maximum and is fixed by convention ↗).

DefinitionDefinition: AI-adaptedProof: Not applicableverified 2026-08-02 (claude-opus-5)Open item page →

Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$

Definition

Let $a, b \in Z$ . An integer $d$ is a common divisor of $a$ and $b$ when $d ∣ a$ and $d ∣ b$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ). Write

$D (a, b) : = {d \in Z : d ∣ a and d ∣ b}$

for the set of common divisors.

Case $(a, b) \neq (0, 0)$ : the greatest element exists. $D (a, b)$ is nonempty, since $1 ∣ a$ and $1 ∣ b$ for every $a$ and $b$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ). It is bounded above: at least one of $a$ and $b$ is nonzero, say $a \neq 0$ (if instead $b \neq 0$ , argue with $b$ throughout), and every $d \in D (a, b)$ divides $a$ , so $d \leq ∣ a ∣$ by If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ . A nonempty set of integers bounded above has a unique greatest element (A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element), and we define

$\gcd (a, b) : = the greatest element of D (a, b) .$

Since $1 \in D (a, b)$ and $\gcd (a, b)$ is greatest, $\gcd (a, b) \geq 1$ ; in particular $\gcd (a, b) > 0$ .

Case $(a, b) = (0, 0)$ : a convention, fixed here. Every integer divides $0$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ), so $D (0, 0) = Z$ , which has no greatest element at all: the clause above defines nothing, and leaving $\gcd (0, 0)$ undefined would put a hole in every identity below. We therefore set

$\gcd (0, 0) : = 0.$

With both cases together, $\gcd (a, b)$ is defined for every pair of integers, and $\gcd (a, b) \geq 0$ always.

Why $0$ , and not some other value. The convention is not arbitrary, and the reasons are recorded here rather than deferred:

It is the greatest common divisor in the divisibility ordering. $0$ is a common divisor of $0$ and $0$ , and every common divisor of $0$ and $0$ divides $0$ . So $0$ is greatest at $(0, 0)$ in the sense "divisible by every common divisor", which is the sense that Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well shows holds at every pair, $(0, 0)$ included, whereas "greatest in the order of $Z$ " fails there.
It is the only value under which the scaling identity extends to this boundary. Requiring $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ to hold at every triple leaves no freedom here. At $c = 0$ with any $(a, b) \neq (0, 0)$ it would read $\gcd (0, 0) = ∣ 0 ∣ \gcd (a, b) = 0$ , whose right-hand side does not involve $\gcd (0, 0)$ at all; and at $a = b = 0$ with $c = 1 + 1$ it reads $g = g + g$ , again giving $g = 0$ . The value is therefore chosen here, and $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all integers $a, b, c$ , the identity holding at $c = 0$ and at $(a, b) = (0, 0)$ as well then proves the identity for every triple with this convention in force; its own $(0, 0)$ case reads the value off this definition rather than establishing it.
It is consistent with the product formula — $\gcd (a, b) lcm (a, b) = ∣ a b ∣$ (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ ) reads $0 \cdot 0 = 0$ at $(0, 0)$ , using $lcm (0, 0) = 0$ from Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ . This one is a check, not a second forcing argument: with $lcm (0, 0) = 0$ the left side vanishes whatever value $\gcd (0, 0)$ is given, so the product formula is silent at $(0, 0)$ and only the scaling identity above pins the value down.

Remarks

The gap the convention fills is real. The failure is exhibited on the companion page by The common divisors of $(0, 0)$ are all of $Z$ and have no greatest element in the order of $Z$ , so $\gcd (0, 0)$ cannot be defined as a maximum and is fixed by convention ↗: the common divisors of $(0, 0)$ really are all of $Z$ , and really have no greatest element, so a value has to be supplied rather than computed.
The definition is by a maximum, and the theory replaces it by a divisibility characterisation. Reading $\gcd$ as "largest common divisor" is what makes the $(0, 0)$ case awkward, and it is also not the property later pages use. Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well proves the replacement: $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d$ is a common divisor, and every common divisor divides $d$ . That statement is uniform across all pairs.
Sign. $\gcd (a, b)$ is never negative, by construction. Since $- d$ is a common divisor whenever $d$ is (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ), the set $D (a, b)$ is symmetric about $0$ , and taking the greatest element is exactly the choice of the nonnegative representative from each pair of associates (For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$ ).
Two arguments, not a list. $\gcd$ is defined here on pairs only. Nothing on this page needs a greatest common divisor of a longer list, and none is defined.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

$\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$

Statement

For all $a, b \in Z$ , with $\gcd$ as in Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ :

$\gcd (a, b) = \gcd (b, a)$ ;
$\gcd (a, b) = \gcd (∣ a ∣, ∣ b ∣)$ ;
$\gcd (a, 0) = ∣ a ∣$ , and in particular $\gcd (0, 0) = 0$ ;
$\gcd (a, 1) = 1$ ;
$\gcd (a, a) = ∣ a ∣$ ;
$\gcd (a, b) \geq 1$ unless $a = b = 0$ , in which case $\gcd (a, b) = 0$ .

Facts & Assumptions

Given: Integers $a$ and $b$ , and the set $D (a, b) = {d : d ∣ a and d ∣ b}$ of common divisors (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L1]

For $(a, b) \neq (0, 0)$ , $\gcd (a, b)$ is the unique greatest element of $D (a, b)$ and satisfies $\gcd (a, b) \geq 1$ ; and $\gcd (0, 0) = 0$ by convention (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L2]

$d ∣ a$ means $a = d q$ for some $q$ ; every $d$ satisfies $d ∣ 0$ ; $0 ∣ a$ only for $a = 0$ ; and $1 ∣ a$ , $a ∣ a$ for every $a$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L3]

$d ∣ a$ , $d ∣ - a$ , $- d ∣ a$ and $- d ∣ - a$ are equivalent (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L4]

If $d ∣ a$ and $a \neq 0$ then $d \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

[L5]

$u ∣ 1$ exactly when $u = 1$ or $u = - 1$ , and $1 \neq - 1$ ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ).

[L6]

[L7]

$Z$ is a commutative ring with $x \cdot 1 = x$ , $x \cdot (- 1) = - x$ and $- (- x) = x$ ; its order is total, antisymmetric, transitive and compatible with addition, and positives are closed under multiplication (The integers form a commutative ring, Arithmetic on the integers, The integers form a totally ordered ring, Order on the integers).

Proof

technique · direct

1.1

$1 \neq 0$ and $- 1 \leq 0 \leq 1$ . If $1 = 0$ then $- 1 = - 0 = 0 = 1$ , contradicting $1 \neq - 1$ . By totality $0 \leq 1$ or $1 \leq 0$ ; in the second case adding $- 1$ gives $0 \leq - 1$ , and $- 1 \neq 0$ , so $0 < - 1$ and hence $0 < (- 1) (- 1) = 1$ , contradicting $1 \leq 0$ by antisymmetry. So $0 \leq 1$ , and adding $- 1$ gives $- 1 \leq 0$ .

L5L7

1.2

$∣ x ∣ ∣ x$ for every $x$ : by totality $x \geq 0$ , when $x = ∣ x ∣ = ∣ x ∣ \cdot 1$ , or $x \leq 0$ , when $∣ x ∣ = - x$ and so $x = - (- x) = - ∣ x ∣ = ∣ x ∣ \cdot (- 1)$ .

L6L7

1.3

For every $d$ and $x$ : $d ∣ x$ if and only if $d ∣ ∣ x ∣$ , because $∣ x ∣$ is $x$ or $- x$ and the two conditions $d ∣ x$ , $d ∣ - x$ are equivalent.

L3L6

1.4

Claim 1. The condition defining $D (a, b)$ is unchanged when $a$ and $b$ are interchanged, so $D (a, b) = D (b, a)$ ; and $(a, b) = (0, 0)$ exactly when $(b, a) = (0, 0)$ . Hence the two greatest elements coincide in the first case, and both values are $0$ in the second.

1.5

Claim 5. $D (a, a) = {d : d ∣ a} = D (a, 0)$ , and $(a, a) = (0, 0)$ exactly when $(a, 0) = (0, 0)$ , so $\gcd (a, a) = \gcd (a, 0)$ .

L1L2

1.6

Claim 6 is [L1] restated: for $(a, b) \neq (0, 0)$ the value $\gcd (a, b)$ is $\geq 1$ because $1$ is a common divisor and $\gcd (a, b)$ is greatest, and at $(0, 0)$ the value is $0$ by convention.

L1L2

2.1

Claim 2. By step 1.3, $D (a, b) = D (∣ a ∣, ∣ b ∣)$ ; and $∣ a ∣ = 0$ exactly when $a = 0$ , so $(a, b) = (0, 0)$ exactly when $(∣ a ∣, ∣ b ∣) = (0, 0)$ . Hence the values agree in both cases.

step 1.3L1L6

2.2

Claim 3. $D (a, 0) = {d : d ∣ a}$ , since every $d$ divides $0$ . If $a = 0$ this is $Z$ and $\gcd (0, 0) = 0 = ∣ 0 ∣$ by the convention. If $a \neq 0$ , then $∣ a ∣ \in D (a, 0)$ by step 1.2, and every $d \in D (a, 0)$ satisfies $d \leq ∣ a ∣$ by [L4], so $∣ a ∣$ is the greatest element of $D (a, 0)$ and $\gcd (a, 0) = ∣ a ∣$ .

step 1.2L1L2L4L6

2.3

Claim 4. Every $d \in D (a, 1)$ satisfies $d ∣ 1$ , hence $d = 1$ or $d = - 1$ ; and $1 \in D (a, 1)$ since $1 ∣ a$ and $1 ∣ 1$ . Also $(a, 1) \neq (0, 0)$ because $1 \neq 0$ . Since $- 1 \leq 1$ by step 1.1, the greatest element of $D (a, 1)$ is $1$ , so $\gcd (a, 1) = 1$ .

step 1.1L1L2L5L7

3.1

Claim 3's second half and claim 5 now read off: $\gcd (0, 0) = 0 = ∣ 0 ∣$ , and $\gcd (a, a) = \gcd (a, 0) = ∣ a ∣$ .

step 2.2step 1.5

4.1

Claims 1 to 6 are established.

step 1.4step 2.1step 2.2step 2.3step 3.1step 1.6∎

Remarks

Claim 2 is what lets every later argument assume the arguments are nonnegative, and claim 1 lets it assume they are in either order. Both are used without comment below.
Every clause is checked at the boundary. Claim 3 covers $a = 0$ , where it returns the convention $\gcd (0, 0) = 0$ rather than contradicting it; claim 4 holds at $a = 0$ , giving $\gcd (0, 1) = 1$ ; and claim 5 holds at $a = 0$ , giving $\gcd (0, 0) = 0$ . There is no pair at which a clause above is silent.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution

Statement

Let $a, b \in Z$ , not both $0$ , and put

$I : = {a x + b y : x, y \in Z} .$

Then $I$ contains a positive element, and its least positive element is $\gcd (a, b)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ). In particular there are integers $x_{0}, y_{0}$ with

$a x_{0} + b y_{0} = \gcd (a, b),$

so the equation $a x + b y = \gcd (a, b)$ is solvable in $Z$ .

Facts & Assumptions

Given: Integers $a$ and $b$ , not both $0$ ; the set $I = {a x + b y : x, y \in Z}$ ; and the embedding $ι : N \to Z$ , $ι (k) = [(k, 0)]$ , of The naturals embed in the integers.

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , $x \cdot 0 = 0$ , multiplication distributes over addition, and every $x$ has an additive inverse $- x$ , with $- (- x) = x$ and $(- x) (- y) = x y$ ; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L2]

[L3]

$ι$ is injective, preserves addition, multiplication and order, and its image is exactly the nonnegative integers (The naturals embed in the integers, The natural numbers $N$ (von Neumann)).

[L4]

Every nonempty subset of $N$ has a least element (The well-ordering principle, Order on the natural numbers).

[L5]

For $a \in Z$ and $b^{'} > 0$ there are integers $q, r$ with $a = q b^{'} + r$ and $0 \leq r < b^{'}$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L6]

For $(a, b) \neq (0, 0)$ , $\gcd (a, b)$ is the unique greatest element of the set $D (a, b)$ of common divisors of $a$ and $b$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L7]

If $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all $x, y$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L8]

[L9]

$∣ x ∣ = x$ when $x \geq 0$ (The absolute value $∣ a ∣$ of an integer); $∣ x ∣ \geq 0$ (Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L10]

$d ∣ a$ means $a = d q$ for some $q \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

Proof

technique · direct

1.1

If $0 \leq u$ and $0 \leq v$ then $0 \leq u v$ , and if moreover $u \neq 0$ and $v \neq 0$ then $0 < u v$ : for $u = 0$ or $v = 0$ the product is $0$ , and otherwise $0 < u$ and $0 < v$ , so $0 < u v$ because positives are closed under multiplication.

L1L2

1.2

If $0 < u$ and $0 \leq v$ then $0 < u + v$ : adding $u$ to $0 \leq v$ gives $u \leq u + v$ , so $0 \leq u + v$ by transitivity, and $u + v = 0$ would give $u \leq 0$ and hence $u = 0$ by antisymmetry, contrary to $0 < u$ .

L1L2

2.1

$x \cdot x \geq 0$ for every $x$ , with $x \cdot x > 0$ when $x \neq 0$ . By totality either $0 \leq x$ , and step 1.1 applies directly, or $x \leq 0$ , in which case $0 \leq - x$ by compatibility with addition and $x \cdot x = (- x) (- x) \geq 0$ by step 1.1; the strict form follows since $x \neq 0$ gives $- x \neq 0$ .

step 1.1L1L2

3.1

$I$ contains a positive element: $a \cdot a + b \cdot b \in I$ , and one of $a, b$ is nonzero, so one of $a \cdot a$ , $b \cdot b$ is positive and the other is nonnegative, whence the sum is positive by step 1.2.

step 2.1step 1.2given

4.1

Let $P$ be the set of positive elements of $I$ and put $T : = {k \in N : ι (k) \in P}$ . Every $p \in P$ satisfies $p \geq 0$ , hence $p = ι (k)$ for some $k \in N$ with $k \in T$ ; so $T$ is nonempty by step 3.1.

step 3.1L3

5.1

By well-ordering let $k_{0}$ be the least element of $T$ and put $d : = ι (k_{0})$ , so $d \in P$ and $d > 0$ ; fix $x_{0}, y_{0} \in Z$ with $d = a x_{0} + b y_{0}$ .

step 4.1L4choose

6.1

$d$ is the least element of $P$ : given $p \in P$ , write $p = ι (k)$ with $k \in T$ as in step 4.1; then $k_{0} \leq k$ , and applying $ι$ , which preserves the order, gives $d = ι (k_{0}) \leq ι (k) = p$ .

step 4.1step 5.1L3L4

7.1

$d ∣ a$ . By [L5] with divisor $d > 0$ write $a = q d + r$ with $0 \leq r < d$ . Then $r = a - q d = a - q (a x_{0} + b y_{0}) = a (1 - q x_{0}) + b (- q y_{0})$ , so $r \in I$ . If $r$ were positive it would lie in $P$ , so $d \leq r$ by step 6.1, which with $r < d$ contradicts antisymmetry. Hence $r$ is not positive; with $0 \leq r$ this forces $r = 0$ , so $a = q d$ and $d ∣ a$ .

step 5.1step 6.1L1L2L5L10

7.2

$d ∣ b$ , by the same argument with $b$ in place of $a$ : dividing $b$ by $d$ gives $b = q^{'} d + r^{'}$ with $0 \leq r^{'} < d$ , and $r^{'} = b (1 - q^{'} y_{0}) + a (- q^{'} x_{0}) \in I$ , so $r^{'} = 0$ as before.

step 5.1step 6.1L1L2L5L10

8.1

So $d$ is a common divisor of $a$ and $b$ . Moreover every common divisor $c$ of $a$ and $b$ divides $a x_{0} + b y_{0} = d$ by [L7].

step 5.1step 7.1step 7.2L7

9.1

Since $d > 0$ we have $d \neq 0$ and $∣ d ∣ = d$ , so every common divisor $c$ satisfies $c \leq ∣ d ∣ = d$ by [L8].

step 5.1step 8.1L8L9

10.1

Therefore $d$ is the greatest element of $D (a, b)$ , and greatest elements are unique, so $d = \gcd (a, b)$ by [L6]; the hypothesis that $a$ and $b$ are not both $0$ is what makes that clause of the definition apply.

step 8.1step 9.1L6given

11.1

Hence $\gcd (a, b) = d$ is the least positive element of $I$ by step 6.1, and $\gcd (a, b) = a x_{0} + b y_{0}$ by step 5.1: the equation $a x + b y = \gcd (a, b)$ is solvable.

step 5.1step 6.1step 10.1∎

Remarks

Where the work is. Two places, and both are easy to hand-wave. The first is that $I$ contains a positive element at all, which is what the hypothesis "not both zero" buys and which is proved through $a \cdot a + b \cdot b$ rather than by taking $∣ a ∣$ (that would need a case split on which of $a$ , $b$ is nonzero). The second is the last inequality: that every common divisor is below $d$ needs If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ , not just $c ∣ d$ , because divisibility is not the order of $Z$ .
The hypothesis cannot be dropped. At $(a, b) = (0, 0)$ the set $I$ is ${0}$ , which has no positive element, so "the least positive element of $I$ " names nothing; that is precisely the pair at which $\gcd$ is fixed by convention (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).
This is an existence statement. The coefficients $x_{0}, y_{0}$ come from a least element supplied by well-ordering, so nothing here computes them. The extended Euclidean algorithm: the same descent produces integers $x, y$ with $a x + b y = \gcd (a, b)$ , so Bézout coefficients are computed and not merely shown to exist does compute them.

CorollaryStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well

Statement

Let $a, b \in Z$ . Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

Consequently, for $d \in Z$ the following are equivalent:

$d = \gcd (a, b)$ ;
$d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ .

This characterisation holds for every pair $(a, b)$ , the pair $(0, 0)$ included, where it returns the value $\gcd (0, 0) = 0$ fixed by convention.

Facts & Assumptions

Given: Integers $a$ and $b$ , and $g : = \gcd (a, b)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L1]

For $(a, b) \neq (0, 0)$ , $g$ is the greatest element of the set $D (a, b)$ of common divisors, so in particular $g \in D (a, b)$ , and $g \geq 1$ ; at $(a, b) = (0, 0)$ , $g = 0$ by convention. In both cases $g \geq 0$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L2]

For $(a, b) \neq (0, 0)$ there are $x_{0}, y_{0} \in Z$ with $a x_{0} + b y_{0} = g$ (Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[L3]

Every integer divides $0$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L4]

If $c ∣ a$ and $c ∣ b$ then $c ∣ a x + b y$ for all $x, y$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L5]

If $u ∣ v$ and $v ∣ u$ then $∣ u ∣ = ∣ v ∣$ (For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$ ).

[L6]

$∣ x ∣ = x$ when $x \geq 0$ (The absolute value $∣ a ∣$ of an integer, Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

Proof

technique · direct

1.1

Suppose $(a, b) \neq (0, 0)$ and let $c$ be a common divisor of $a$ and $b$ . By [L2] fix $x_{0}, y_{0}$ with $a x_{0} + b y_{0} = g$ ; then $c ∣ g$ by [L4].

L2L4

1.2

Suppose instead $(a, b) = (0, 0)$ . Then $g = 0$ , and every integer, in particular every common divisor $c$ , divides $0 = g$ .

L1L3

1.3

$g$ itself is a common divisor of $a$ and $b$ : for $(a, b) \neq (0, 0)$ this is $g \in D (a, b)$ , and for $(a, b) = (0, 0)$ it is $0 ∣ 0$ . And $g \geq 0$ in both cases.

L1L3

2.1

In both cases every common divisor of $a$ and $b$ divides $g$ ; since the two cases are exhaustive, this is the first assertion.

step 1.1step 1.2

3.1

Claim 1 implies claim 2: if $d = g$ then $d \geq 0$ , $d ∣ a$ and $d ∣ b$ by step 1.3, and every common divisor divides $d$ by step 2.1.

step 2.1step 1.3

3.2

Claim 2 implies claim 1: suppose $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ . Then $d$ is a common divisor, so $d ∣ g$ by step 2.1; and $g$ is a common divisor by step 1.3, so $g ∣ d$ by hypothesis. Hence $∣ d ∣ = ∣ g ∣$ by [L5], and since $d \geq 0$ and $g \geq 0$ this reads $d = ∣ d ∣ = ∣ g ∣ = g$ .

step 2.1step 1.3L1L5L6

4.1

The two claims are therefore equivalent, for every pair $(a, b)$ including $(0, 0)$ , where step 1.2 and step 1.3 were proved directly from the convention rather than from a maximum.

step 1.2step 1.3step 3.1step 3.2∎

Remarks

This is the statement later pages should cite. "Greatest in the order of $Z$ " is how $\gcd$ was defined, but it is not a property that survives at $(0, 0)$ and it is not what any later argument uses. "Nonnegative, a common divisor, and divisible by every common divisor" is uniform, and it is the definition that generalises beyond $Z$ .
Both halves of claim 2 are needed. Dropping $d \geq 0$ leaves $d$ determined only up to sign, since $- g$ also divides $a$ and $b$ and is divided by every common divisor (For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$ ). Dropping "every common divisor divides $d$ " leaves every nonnegative common divisor a candidate.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

If $a = q b + r$ then $a, b$ and $b, r$ have exactly the same common divisors, so $\gcd (a, b) = \gcd (b, r)$

Statement

Let $a, b, q, r \in Z$ satisfy

$a = q b + r .$

Then an integer $d$ is a common divisor of $a$ and $b$ if and only if it is a common divisor of $b$ and $r$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ); the two sets of common divisors are equal. Consequently

$\gcd (a, b) = \gcd (b, r)$

(Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

No inequality on $r$ is assumed: the identity $a = q b + r$ alone is what is used, so the lemma applies to any decomposition of $a$ , not only to the one produced by division with remainder.

Facts & Assumptions

Given: Integers $a, b, q, r$ with $a = q b + r$ , and the sets $D (a, b)$ and $D (b, r)$ of common divisors (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L1]

$Z$ is a commutative ring: $x \cdot 0 = 0$ , $x + 0 = x$ , and every $x$ has an additive inverse; we write $u - v$ for $u + (- v)$ , and $a = q b + r$ gives $r = a - q b$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

If $d ∣ u$ and $d ∣ v$ then $d ∣ u x + v y$ for all $x, y$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L3]

For $(u, v) \neq (0, 0)$ , $\gcd (u, v)$ is the greatest element of $D (u, v)$ , and $\gcd (0, 0) = 0$ by convention (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

Proof

technique · direct

1.1

Suppose $d ∣ b$ and $d ∣ r$ . Then $d ∣ b q + r \cdot 1 = a$ by [L2], so $d$ is a common divisor of $a$ and $b$ : $D (b, r) \subseteq D (a, b)$ .

givenL1L2

1.2

Suppose $d ∣ a$ and $d ∣ b$ . Then $d ∣ a \cdot 1 + b (- q) = a - q b = r$ by [L2], so $d$ is a common divisor of $b$ and $r$ : $D (a, b) \subseteq D (b, r)$ .

givenL1L2

1.3

The pairs vanish together: if $b = 0$ and $r = 0$ then $a = q \cdot 0 + 0 = 0$ , and if $a = 0$ and $b = 0$ then $r = a - q b = 0 - 0 = 0$ . So $(a, b) = (0, 0)$ exactly when $(b, r) = (0, 0)$ .

givenL1

2.1

By steps 1.1 and 1.2 the two sets of common divisors are equal, $D (a, b) = D (b, r)$ .

step 1.1step 1.2

3.1

If $(a, b) \neq (0, 0)$ then also $(b, r) \neq (0, 0)$ by step 1.3, and both greatest common divisors are the greatest element of the one set $D (a, b) = D (b, r)$ , hence equal. If $(a, b) = (0, 0)$ then $(b, r) = (0, 0)$ and both values are $0$ . In either case $\gcd (a, b) = \gcd (b, r)$ .

step 1.3step 2.1L3∎

Remarks

This is the whole content of the Euclidean algorithm; everything else in The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ is bookkeeping about termination. Each division replaces a pair by a strictly smaller one without changing the set of common divisors, so the invariant is not merely the value $\gcd$ but the set $D$ itself.
The absence of a constraint on $r$ matters. Applying the lemma with $q = 1$ and no inequality is exactly what identifies $\gcd (F_{n + 2}, F_{n + 1})$ with $\gcd (F_{n + 1}, F_{n})$ for consecutive Fibonacci numbers, where $F_{n + 2} = F_{n + 1} + F_{n}$ is given by the recursion and not by a division.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$

Statement

Let $a \in Z$ and $b > 0$ . Define $Φ : Z \times Z \to Z \times Z$ by

$Φ (u, v) = {\begin{cases} (v, u - q v) & if v > 0, \\ (u, v) & if v \leq 0, \end{cases}$

where in the first clause $q$ is the unique quotient of $u$ by $v$ given by Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ , so that $u - q v$ is the remainder and $0 \leq u - q v < v$ .

Let $R : N \to Z \times Z$ be the unique function with $R (0) = (a, b)$ and $R (σ (k)) = Φ (R (k))$ supplied by the recursion theorem (The recursion theorem). Write $R (k) = (a_{k}, b_{k})$ ; the sequence $b_{0}, b_{1}, b_{2}, \dots$ is the remainder descent from $(a, b)$ .

Then:

$b_{k} \geq 0$ for every $k$ , and $b_{σ (k)} < b_{k}$ whenever $b_{k} > 0$ ;
$\gcd (a_{k}, b_{k}) = \gcd (a, b)$ for every $k$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ );
there is a least $N \in N$ with $b_{N} = 0$ , and $N \neq 0$ ; writing $N = σ (M)$ , the value $b_{M}$ is the last nonzero remainder, and $b_{M} > 0$ ;
$a_{N} = b_{M} = \gcd (a, b)$ .

So the descent terminates, and the last nonzero remainder is $\gcd (a, b)$ .

Facts & Assumptions

Given: $a \in Z$ , $b > 0$ , the map $Φ$ and the sequence $R (k) = (a_{k}, b_{k})$ described above, and the embedding $ι : N \to Z$ , $ι (k) = [(k, 0)]$ , of The naturals embed in the integers.

[L1]

$Z$ is a commutative ring; its order is total, antisymmetric and transitive, and is compatible with addition; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a commutative ring, Arithmetic on the integers, The integers form a totally ordered ring, Order on the integers, The integers as equivalence classes of pairs of naturals).

[L2]

For $u \in Z$ and $v > 0$ there is exactly one pair $(q, r)$ of integers with $u = q v + r$ and $0 \leq r < v$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L3]

For a set $A$ , an $α \in A$ and a function $f : A \to A$ there is exactly one $g : N \to A$ with $g (0) = α$ and $g (σ (k)) = f (g (k))$ (The recursion theorem).

[L4]

Induction on $N$ : a property holding at $0$ and inherited by successors holds everywhere (The principle of mathematical induction).

[L5]

Every nonempty subset of $N$ has a least element (The well-ordering principle, Order on the natural numbers, The natural numbers $N$ (von Neumann)).

[L6]

$ι$ is injective, preserves addition, multiplication and order, and its image is exactly the nonnegative integers (The naturals embed in the integers).

[L7]

On $N$ : exactly one of $m < n$ , $m = n$ , $n < m$ holds (Trichotomy of the order on $N$ ); $m < n$ if and only if $σ (m) \leq n$ (Discreteness: $σ (n)$ is the immediate successor); and every $n \neq 0$ is a successor (Every nonzero natural number is a successor).

[L8]

If $u = q v + r$ then $\gcd (u, v) = \gcd (v, r)$ (If $a = q b + r$ then $a, b$ and $b, r$ have exactly the same common divisors, so $\gcd (a, b) = \gcd (b, r)$ ).

[L9]

$\gcd (u, 0) = ∣ u ∣$ , and $∣ u ∣ = u$ when $u \geq 0$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ , The absolute value $∣ a ∣$ of an integer, Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

Proof

technique · induction

1.1

$Φ$ is a well-defined function. For $v > 0$ the pair $(q, r)$ with $u = q v + r$ and $0 \leq r < v$ is unique by [L2], so $q$ and $r = u - q v$ depend only on $(u, v)$ ; for $v \leq 0$ the value is $(u, v)$ ; and the two clauses are exhaustive and exclusive by totality. Hence [L3] applies with $A = Z \times Z$ , $α = (a, b)$ and $f = Φ$ , giving the sequence $R$ .

L1L2L3construct

1.2

Base case of the induction, at $k = 0$ : $b_{0} = b > 0$ , so $b_{0} \geq 0$ ; and $\gcd (a_{0}, b_{0}) = \gcd (a, b)$ because $(a_{0}, b_{0}) = (a, b)$ .

basegivenL1

1.3

Induction hypothesis: fix $k$ and assume $b_{k} \geq 0$ and $\gcd (a_{k}, b_{k}) = \gcd (a, b)$ .

2.1

Inductive step. If $b_{k} > 0$ , then by [L2] write $a_{k} = q b_{k} + r$ with $0 \leq r < b_{k}$ ; by definition $R (σ (k)) = Φ (a_{k}, b_{k}) = (b_{k}, r)$ , so $b_{σ (k)} = r \geq 0$ and $b_{σ (k)} = r < b_{k}$ , while $\gcd (a_{σ (k)}, b_{σ (k)}) = \gcd (b_{k}, r) = \gcd (a_{k}, b_{k}) = \gcd (a, b)$ by [L8]. If instead $b_{k} = 0$ , then $b_{k} \leq 0$ , so $R (σ (k)) = R (k)$ and both properties are inherited unchanged. Since $b_{k} \geq 0$ , these two cases are exhaustive.

step 1.3L1L2L8

3.1

By induction, $b_{k} \geq 0$ and $\gcd (a_{k}, b_{k}) = \gcd (a, b)$ for every $k \in N$ ; and step 2.1 also shows $b_{σ (k)} < b_{k}$ whenever $b_{k} > 0$ . This is claim 1 and claim 2.

step 1.2step 2.1L4

4.1

Let $U : = {n \in N : ι (n) = b_{k} for some k \in N}$ . Every $b_{k}$ is nonnegative, hence lies in the image of $ι$ , so $U$ is nonempty; let $n_{0}$ be its least element and fix $k_{0}$ with $b_{k_{0}} = ι (n_{0})$ .

step 3.1L5L6choose

5.1

$b_{k_{0}} = 0$ . Otherwise $b_{k_{0}} > 0$ , so $0 \leq b_{σ (k_{0})} < b_{k_{0}}$ by step 3.1; writing $b_{σ (k_{0})} = ι (n_{1})$ with $n_{1} \in U$ , we get $ι (n_{1}) < ι (n_{0})$ , and hence $n_{1} < n_{0}$ , since otherwise $n_{0} \leq n_{1}$ by trichotomy and so $ι (n_{0}) \leq ι (n_{1})$ , contradicting antisymmetry. That contradicts the minimality of $n_{0}$ .

step 3.1step 4.1L1L6L7

6.1

So ${k \in N : b_{k} = 0}$ is nonempty; let $N$ be its least element. $N \neq 0$ , since $b_{0} = b > 0$ . Hence $N = σ (M)$ for some $M \in N$ , and $M < N$ because $M < σ (M)$ .

step 5.1givenL5L7

7.1

$b_{M} > 0$ : indeed $b_{M} \geq 0$ by step 3.1, and $b_{M} \neq 0$ because $M < N$ and $N$ is the least index with vanishing $b$ .

step 3.1step 6.1

8.1

Since $b_{M} > 0$ , the definition gives $R (N) = R (σ (M)) = Φ (a_{M}, b_{M}) = (b_{M}, a_{M} - q b_{M})$ , so $a_{N} = b_{M}$ and $b_{N} = a_{M} - q b_{M}$ ; and $b_{N} = 0$ by the choice of $N$ .

step 6.1step 7.1L2

9.1

Therefore $\gcd (a, b) = \gcd (a_{N}, b_{N}) = \gcd (a_{N}, 0) = ∣ a_{N} ∣ = a_{N} = b_{M}$ , the last equality because $a_{N} = b_{M} > 0$ . So the descent terminates at index $N$ and the last nonzero remainder $b_{M}$ equals $\gcd (a, b)$ , which is claims 3 and 4.

step 3.1step 7.1step 8.1L9discharge-induction∎

Remarks

Termination is not an extra appeal to well-ordering about $Z$ . It is the clause $0 \leq r < v$ of Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ , which makes the second coordinates a strictly decreasing sequence of nonnegative integers; well-ordering is then applied to their preimages in $N$ , where it is available.
The theorem is stated for $b > 0$ only, matching Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ . For $b < 0$ one may run the descent from $(a, ∣ b ∣)$ instead: $\gcd (a, b) = \gcd (a, ∣ b ∣)$ by $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ , so nothing is lost. That reduction is recorded here rather than built into the statement, so that the recursion above uses the published division algorithm exactly as stated.
No claim is made about how many divisions the descent takes. The count depends on the pair; the companion page works out one family where it is exactly known (Consecutive Fibonacci numbers are coprime, and for every $m \in N$ the Euclidean algorithm on $(F_{m + 3}, F_{m + 2})$ takes exactly $m + 1$ divisions, with quotient $1$ in the first $m$ of them and quotient $2$ in the last ↗), and no worst-case bound over all inputs is proved anywhere here.

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

The extended Euclidean algorithm: the same descent produces integers $x, y$ with $a x + b y = \gcd (a, b)$ , so Bézout coefficients are computed and not merely shown to exist

Statement

Let $a \in Z$ and $b > 0$ , and let $R (k) = (a_{k}, b_{k})$ and $N$ be the remainder descent and its terminating index from The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ . Define $Ψ : Z^{6} \to Z^{6}$ by

$Ψ (A, B, x, y, u, v) = {\begin{cases} (B, A - q B, u, v, x - q u, y - q v) & if B > 0, \\ (A, B, x, y, u, v) & if B \leq 0, \end{cases}$

where in the first clause $q$ is the unique quotient of $A$ by $B$ given by Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ . Let

$S : N \to Z^{6}, S (0) = (a, b, 1, 0, 0, 1), S (σ (k)) = Ψ (S (k))$

be the function supplied by the recursion theorem (The recursion theorem), and write $S (k) = (A_{k}, B_{k}, x_{k}, y_{k}, u_{k}, v_{k})$ . Then for every $k \in N$

$(A_{k}, B_{k}) = (a_{k}, b_{k}), A_{k} = a x_{k} + b y_{k}, B_{k} = a u_{k} + b v_{k} .$

In particular, at the terminating index $N$ ,

$a x_{N} + b y_{N} = A_{N} = a_{N} = \gcd (a, b),$

so the descent that computes $\gcd (a, b)$ computes a pair of Bézout coefficients alongside it.

Facts & Assumptions

Given: $a \in Z$ , $b > 0$ , the descent $R (k) = (a_{k}, b_{k})$ and terminating index $N$ of The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ , and the map $Ψ$ and sequence $S (k) = (A_{k}, B_{k}, x_{k}, y_{k}, u_{k}, v_{k})$ described above.

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , $x \cdot 0 = 0$ , multiplication distributes over addition, and every $x$ has an additive inverse; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L2]

For $A^{'} \in Z$ and $B^{'} > 0$ there is exactly one pair $(q, r)$ of integers with $A^{'} = q B^{'} + r$ and $0 \leq r < B^{'}$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L3]

For a set $X$ , an $α \in X$ and $f : X \to X$ there is exactly one $g : N \to X$ with $g (0) = α$ and $g (σ (k)) = f (g (k))$ (The recursion theorem, The natural numbers $N$ (von Neumann)).

[L4]

Induction on $N$ (The principle of mathematical induction).

[L5]

The descent satisfies $R (0) = (a, b)$ ; $b_{k} \geq 0$ for every $k$ ; $R (σ (k)) = (b_{k}, a_{k} - q b_{k})$ with $q$ the quotient of $a_{k}$ by $b_{k}$ when $b_{k} > 0$ , and $R (σ (k)) = R (k)$ when $b_{k} = 0$ ; $N$ is the least index with $b_{N} = 0$ ; and $a_{N} = \gcd (a, b)$ (The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ , Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L6]

The order on $Z$ is total and antisymmetric; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

Proof

technique · induction

1.1

$Ψ$ is a well-defined function: for $B > 0$ the quotient $q$ of $A$ by $B$ is unique by [L2], so the first clause depends only on the argument; the second clause is the identity; and the two conditions $B > 0$ and $B \leq 0$ are exhaustive and exclusive by totality. So [L3] applies with $X = Z^{6}$ and produces $S$ .

L1L2L3L6construct

1.2

Base case, $k = 0$ : $(A_{0}, B_{0}) = (a, b) = (a_{0}, b_{0})$ ; and $A_{0} = a = a \cdot 1 + b \cdot 0 = a x_{0} + b y_{0}$ , $B_{0} = b = a \cdot 0 + b \cdot 1 = a u_{0} + b v_{0}$ .

basegivenL1L5

1.3

Induction hypothesis: fix $k$ and assume $(A_{k}, B_{k}) = (a_{k}, b_{k})$ , $A_{k} = a x_{k} + b y_{k}$ and $B_{k} = a u_{k} + b v_{k}$ .

2.1

Inductive step, case $b_{k} > 0$ . Then $B_{k} = b_{k} > 0$ , so both recursions take their first clause with the same divisor and the same dividend, hence with the same quotient $q$ by [L2]. Therefore $(A_{σ (k)}, B_{σ (k)}) = (B_{k}, A_{k} - q B_{k}) = (b_{k}, a_{k} - q b_{k}) = (a_{σ (k)}, b_{σ (k)})$ .

step 1.3L2L5

2.2

Inductive step, case $b_{k} = 0$ . Then $B_{k} = b_{k} = 0$ , so $B_{k} \leq 0$ and $S (σ (k)) = S (k)$ , while $R (σ (k)) = R (k)$ ; all three equalities are inherited unchanged. Since $b_{k} \geq 0$ , the two cases are exhaustive.

step 1.3L5L6

3.1

Back in the case $b_{k} > 0$ of step 2.1, the coefficients transport: $A_{σ (k)} = B_{k} = a u_{k} + b v_{k} = a x_{σ (k)} + b y_{σ (k)}$ , since $(x_{σ (k)}, y_{σ (k)}) = (u_{k}, v_{k})$ ; and $B_{σ (k)} = A_{k} - q B_{k} = (a x_{k} + b y_{k}) - q (a u_{k} + b v_{k}) = a (x_{k} - q u_{k}) + b (y_{k} - q v_{k}) = a u_{σ (k)} + b v_{σ (k)}$ by distributivity.

step 1.3step 2.1L1

4.1

By induction the three equalities hold for every $k \in N$ .

step 1.2step 2.1step 3.1step 2.2L4

5.1

At the terminating index $N$ this reads $a x_{N} + b y_{N} = A_{N} = a_{N} = \gcd (a, b)$ , so $(x_{N}, y_{N})$ is a pair of Bézout coefficients for $a$ and $b$ , obtained from the descent itself.

step 4.1L5discharge-induction∎

Remarks

What "computed" means here. The coefficients are produced by a recursion over $N$ whose every step is an application of the division algorithm and four ring operations; nothing in the argument appeals to the existence of a least element of a set. That is the difference from Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution, where the coefficients come from a well-ordering argument and the proof gives no way to find them.
The Bézout pair produced is not the only one. The companion page records the full family of solutions and a second pair for the same equation (Bézout coefficients are not unique: $1071 \cdot (- 3) + 462 \cdot 7 = 21$ and $1071 \cdot 19 + 462 \cdot (- 44) = 21$ , and for nonzero $a, b$ every solution has the form $(x_{0} + t b / d, y_{0} - t a / d)$ ↗).
Only the first four coordinates of $S$ are needed for the conclusion; the last two are carried because the recursion for $(x, y)$ reads off the previous values of $(u, v)$ , which is what makes the whole thing a single application of the recursion theorem instead of a mutual recursion.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Coprime integers: $\gcd (a, b) = 1$

Definition

Integers $a$ and $b$ are coprime, or relatively prime, when

$\gcd (a, b) = 1$

(Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ). The relation is symmetric, since $\gcd (a, b) = \gcd (b, a)$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ ), and unchanged by signs, since $\gcd (a, b) = \gcd (∣ a ∣, ∣ b ∣)$ .

Boundary values. $N$ contains $0$ and $Z$ contains $0$ and $1$ , so the three degenerate pairs are recorded explicitly, each read off $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ :

$a$ and $1$ are coprime for every integer $a$ , since $\gcd (a, 1) = 1$ ; in particular $0$ and $1$ are coprime.
$0$ and $b$ are coprime exactly when $b = 1$ or $b = - 1$ . Indeed $\gcd (0, b) = \gcd (b, 0) = ∣ b ∣$ , so coprimality says $∣ b ∣ = 1$ , and by Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ together with the case split of The absolute value $∣ a ∣$ of an integer this holds exactly for $b = 1$ and $b = - 1$ , the two units of $Z$ ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ).
$0$ and $0$ are not coprime, since $\gcd (0, 0) = 0$ by the convention of Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , and $0 \neq 1$ : if $1$ were $0$ then $- 1 = - 0 = 0 = 1$ , contradicting the two units being distinct ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ).

Remarks

Coprime is a statement about the pair, not about either integer. Neither $a$ nor $b$ need be prime, and primality is not defined anywhere on this page: $4$ and $9$ are coprime and neither is prime. What coprimality says is that the only common divisors are the units $1$ and $- 1$ ( $a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$ ).
Why it is worth a name before primes appear. The lemma that carries the weight in elementary number theory — if $a ∣ b c$ and $a$ is coprime to $b$ then $a ∣ c$ (If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ) — needs coprimality and no primality at all. Primes enter later, and their key property is a special case of that lemma rather than an independent fact.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

$a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$

Statement

Let $a, b \in Z$ . Then $a$ and $b$ are coprime (Coprime integers: $\gcd (a, b) = 1$ ) if and only if

$a x + b y = 1 for some x, y \in Z .$

When this holds, the set of common divisors of $a$ and $b$ is exactly ${1, - 1}$ .

Facts & Assumptions

Given: Integers $a$ and $b$ .

[L1]

$a$ and $b$ are coprime when $\gcd (a, b) = 1$ (Coprime integers: $\gcd (a, b) = 1$ , Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L2]

For $(a, b) \neq (0, 0)$ there are $x_{0}, y_{0}$ with $a x_{0} + b y_{0} = \gcd (a, b)$ (Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[L3]

$d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ (Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well).

[L4]

If $c ∣ a$ and $c ∣ b$ then $c ∣ a x + b y$ for all $x, y$ ; and $1 ∣ a$ for every $a$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L5]

$c ∣ 1$ exactly when $c = 1$ or $c = - 1$ , and $1 \neq - 1$ ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ).

[L6]

$Z$ is a commutative ring, with $x \cdot 0 = 0$ , $x + 0 = x$ , $- (- x) = x$ and $(- x) (- y) = x y$ (The integers form a commutative ring, Arithmetic on the integers); its order is total, antisymmetric and transitive and is compatible with addition, and positives are closed under multiplication (The integers form a totally ordered ring, Order on the integers).

[L7]

$\gcd (0, 0) = 0$ by convention (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

Proof

technique · direct

1.1

$1 \neq 0$ and $0 \leq 1$ . If $1 = 0$ then $- 1 = - 0 = 0 = 1$ , contradicting $1 \neq - 1$ in [L5]. By totality either $0 \leq 1$ or $1 \leq 0$ ; in the second case adding $- 1$ gives $0 \leq - 1$ , and $- 1 \neq 0$ since otherwise $1 = 0$ , so $0 < - 1$ and hence $0 < (- 1) (- 1) = 1$ , which with $1 \leq 0$ contradicts antisymmetry.

L5L6

1.2

Conversely, suppose $a x + b y = 1$ for some $x, y$ . Every common divisor $c$ of $a$ and $b$ divides $a x + b y = 1$ by [L4], hence $c = 1$ or $c = - 1$ by [L5].

L4L5

2.1

Suppose $a$ and $b$ are coprime, so $\gcd (a, b) = 1$ . Then $(a, b) \neq (0, 0)$ , since $\gcd (0, 0) = 0 \neq 1$ ; so [L2] supplies $x_{0}, y_{0}$ with $a x_{0} + b y_{0} = \gcd (a, b) = 1$ .

step 1.1L1L2L7

2.2

The integer $1$ then satisfies all four conditions of [L3]: $1 \geq 0$ by step 1.1, $1 ∣ a$ and $1 ∣ b$ by [L4], and every common divisor of $a$ and $b$ divides $1$ by step 1.2. Hence $\gcd (a, b) = 1$ , that is, $a$ and $b$ are coprime.

step 1.1step 1.2L1L3L4

3.1

So coprimality and the solvability of $a x + b y = 1$ are equivalent, by step 2.1 and step 2.2.

step 2.1step 2.2

4.1

When they hold, step 1.2 shows every common divisor is $1$ or $- 1$ ; conversely $1$ and $- 1$ are common divisors of any pair, since $1 ∣ a$ , $1 ∣ b$ , $- 1 ∣ a$ and $- 1 ∣ b$ . So the set of common divisors is exactly ${1, - 1}$ , and it has two elements since $1 \neq - 1$ .

step 1.2L4L5∎

Remarks

The criterion is the practical form of coprimality. Verifying $\gcd (a, b) = 1$ from the definition means examining all common divisors; exhibiting one pair $(x, y)$ with $a x + b y = 1$ settles it in a line, and the extended Euclidean algorithm produces such a pair (The extended Euclidean algorithm: the same descent produces integers $x, y$ with $a x + b y = \gcd (a, b)$ , so Bézout coefficients are computed and not merely shown to exist).
The analogous statement with $1$ replaced by a general $c$ is false, and the correct version is that $a x + b y = c$ is solvable exactly when $\gcd (a, b) ∣ c$ ; that is worked out on the companion page ( $a x + b y = c$ has an integer solution exactly when $\gcd (a, b) ∣ c$ : $6 x + 15 y = 9$ is solvable and $6 x + 15 y = 7$ is not ↗).

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$

Statement

Let $a, b, c \in Z$ .

If $\gcd (a, b) = 1$ and $a ∣ b c$ , then $a ∣ c$ .
If $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ , then $a b ∣ c$ .

Facts & Assumptions

Given: Integers $a, b, c$ .

[L1]

$a$ and $b$ are coprime exactly when $\gcd (a, b) = 1$ , and this holds exactly when $a x + b y = 1$ for some $x, y \in Z$ (Coprime integers: $\gcd (a, b) = 1$ , $a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$ , Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L2]

$\gcd (a, b) = \gcd (b, a)$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ ).

[L3]

Divisibility is reflexive and transitive; if $d ∣ u$ and $d ∣ v$ then $d ∣ u x + v y$ for all $x, y$ ; and $d ∣ u$ implies $d ∣ u w$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L4]

$d ∣ u$ means $u = d q$ for some $q \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L5]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x \cdot 1 = x$ , and multiplication distributes over addition (The integers form a commutative ring, Arithmetic on the integers).

Proof

technique · direct

1.1

Claim 1. Assume $\gcd (a, b) = 1$ and $a ∣ b c$ , and fix $x, y$ with $a x + b y = 1$ .

L1choose

1.2

Claim 2. Assume $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ . Write $c = a s$ with $s \in Z$ .

L4choose

2.1

Multiplying $a x + b y = 1$ by $c$ gives $a (x c) + (b c) y = c$ , using associativity, commutativity and distributivity.

step 1.1L5

3.1

Now $a ∣ a$ , hence $a ∣ a (x c)$ by [L3]; and $a ∣ b c$ , hence $a ∣ (b c) y$ by [L3]. Applying linearity to these two with coefficients $1$ and $1$ gives $a ∣ a (x c) + (b c) y = c$ .

step 1.1step 2.1L3L5

4.1

Then $b ∣ c = a s$ , and $\gcd (b, a) = \gcd (a, b) = 1$ by [L2], so claim 1 applied with $b$ , $a$ , $s$ in place of $a$ , $b$ , $c$ gives $b ∣ s$ .

step 3.1step 1.2L2

5.1

Write $s = b t$ ; then $c = a s = a (b t) = (a b) t$ , so $a b ∣ c$ .

step 1.2step 4.1L4L5∎

Remarks

No primality is used. Claim 1 is exactly the statement usually met as Euclid's lemma with $a$ prime; what the proof needs is coprimality of $a$ with $b$ , and primality of $a$ enters only later, as a way of guaranteeing that coprimality. This is why the lemma is homed here rather than with the primes.
Coprimality is essential in both claims. Without it, $6 ∣ 4 \cdot 9$ while $6$ divides neither factor ( $6 ∣ 4 \cdot 9$ while $6 ∤ 4$ and $6 ∤ 9$ : dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails ↗); and $2 ∣ 4$ , $4 ∣ 4$ but $2 \cdot 4 = 8 ∤ 4$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

$\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all integers $a, b, c$ , the identity holding at $c = 0$ and at $(a, b) = (0, 0)$ as well

Statement

For all $a, b, c \in Z$ ,

$\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$

(Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , The absolute value $∣ a ∣$ of an integer). The identity is asserted for every triple, including $c = 0$ and $(a, b) = (0, 0)$ , where both sides are $0$ .

Facts & Assumptions

Given: Integers $a, b, c$ , and $g : = \gcd (a, b)$ , $h : = \gcd (c a, c b)$ .

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x \cdot 0 = 0$ , $x \cdot 1 = x$ , $x \cdot (- 1) = - x$ , multiplication distributes over addition, and every $x$ has an additive inverse, with $- (- x) = x$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

[L3]

$\gcd (u, v) \geq 0$ always, with $\gcd (u, v) \geq 1$ when $(u, v) \neq (0, 0)$ and $\gcd (0, 0) = 0$ by convention; $\gcd (u, v)$ is a common divisor of $u$ and $v$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L4]

Every common divisor of $u$ and $v$ divides $\gcd (u, v)$ (Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well).

[L5]

For $(u, v) \neq (0, 0)$ there are $x_{0}, y_{0}$ with $u x_{0} + v y_{0} = \gcd (u, v)$ (Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[L6]

If $d ∣ u$ and $d ∣ v$ then $d ∣ u x + v y$ for all $x, y$ ; and $d ∣ u$ implies $d ∣ u w$ and $- d ∣ u$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L7]

If $d ∣ u$ and $u \neq 0$ then $∣ d ∣ \leq ∣ u ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ); $d ∣ u$ means $u = d q$ for some $q$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L8]

$∣ x ∣ \geq 0$ ; $∣ x ∣ = 0$ exactly when $x = 0$ ; $∣ x ∣ = x$ when $x \geq 0$ ; and $x$ is $∣ x ∣$ or $- ∣ x ∣$ (The absolute value $∣ a ∣$ of an integer, Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L9]

A product of two nonzero integers is nonzero (The integers have no zero divisors; multiplicative cancellation).

Proof

technique · cases

1.1

If $0 \leq u$ and $0 \leq v$ then $0 \leq u v$ : for $u = 0$ or $v = 0$ the product is $0$ , and otherwise $0 < u$ and $0 < v$ , so $0 < u v$ .

L1L2

1.2

Case $c = 0$ : then $c a = c b = 0$ , so the left side is $\gcd (0, 0) = 0$ ; and $∣ c ∣ = ∣ 0 ∣ = 0$ , so the right side is $0 \cdot g = 0$ .

assume-case zeroL1L3L8

1.3

Case $(a, b) = (0, 0)$ : then $c a = c b = 0$ , so the left side is $\gcd (0, 0) = 0$ ; and $g = \gcd (0, 0) = 0$ , so the right side is $∣ c ∣ \cdot 0 = 0$ .

assume-case originL1L3

1.4

Case $c \neq 0$ and $(a, b) \neq (0, 0)$ . Then $g \geq 1$ , and one of $a, b$ is nonzero, say $a \neq 0$ ; so $c a \neq 0$ by [L9] and hence $(c a, c b) \neq (0, 0)$ and $h \geq 1$ . Also $∣ c ∣ \neq 0$ , and $∣ c ∣ g \neq 0$ by [L9].

assume-case genericL3L8L9

2.1

In the case of step 1.4, $∣ c ∣ g$ is a common divisor of $c a$ and $c b$ . Indeed $g ∣ a$ , say $a = g a_{1}$ ; then $c a = c g a_{1}$ , and $c$ is $∣ c ∣$ or $- ∣ c ∣$ by [L8], so $c a = ∣ c ∣ g a_{1}$ or $c a = ∣ c ∣ g (- a_{1})$ , and in either case $∣ c ∣ g ∣ c a$ . The same argument with $b$ gives $∣ c ∣ g ∣ c b$ .

step 1.4L1L3L7L8

2.2

Conversely, by [L5] fix $x_{0}, y_{0}$ with $a x_{0} + b y_{0} = g$ ; multiplying by $c$ gives $(c a) x_{0} + (c b) y_{0} = c g$ . Since $h ∣ c a$ and $h ∣ c b$ , [L6] gives $h ∣ c g$ ; and $∣ c ∣ g$ is $c g$ or $- c g$ , because $∣ c ∣$ is $c$ or $- c$ , so $h ∣ ∣ c ∣ g$ as well.

step 1.4L1L3L5L6L8

3.1

Hence $∣ c ∣ g ∣ h$ by [L4].

step 2.1L4

4.1

Both $h$ and $∣ c ∣ g$ are nonzero by step 1.4, and both are nonnegative, $h$ by [L3] and $∣ c ∣ g$ by step 1.1 and [L8]. From $h ∣ ∣ c ∣ g$ and $∣ c ∣ g \neq 0$ , [L7] gives $∣ h ∣ \leq ∣ ∣ c ∣ g ∣ = ∣ c ∣ g$ , that is $h \leq ∣ c ∣ g$ ; from $∣ c ∣ g ∣ h$ and $h \neq 0$ , [L7] gives $∣ c ∣ g \leq ∣ h ∣ = h$ .

step 1.1step 1.4step 3.1step 2.2L3L7L8

5.1

By antisymmetry $h = ∣ c ∣ g$ in the case of step 1.4.

step 4.1L2

6.1

The three cases of steps 1.2, 1.3 and 1.4 exhaust the possibilities, since either $c = 0$ , or $(a, b) = (0, 0)$ , or neither; so $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all $a, b, c$ .

step 1.2step 1.3step 5.1cases-exhaustive∎

Remarks

The boundary cases are the point, not an aside. The convention $\gcd (0, 0) = 0$ is the only value under which this identity extends to $(a, b) = (0, 0)$ : it would read $\gcd (0, 0) = ∣ c ∣ \gcd (0, 0)$ for every $c$ , and taking $∣ c ∣ = 1 + 1$ gives $\gcd (0, 0) = 0$ . That is a constraint on the choice, not a derivation from this lemma — steps 1.2 and 1.3 above read the boundary value off the convention rather than proving it. The choice is made where the convention is fixed (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ) and instantiated on the companion page ( $\gcd$ at the boundary: $\gcd (a, 0) = ∣ a ∣$ , $\gcd (0, 0) = 0$ , and the convention $\gcd (0, 0) = 0$ is exactly what makes $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ true at $c = 0$ ↗).
Why $∣ c ∣$ and not $c$ . $\gcd$ is nonnegative by construction, so the right side must be too; with $c < 0$ and $g > 0$ the product $c g$ is negative and could not be a greatest common divisor.

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime

Statement

Let $a, b \in Z$ and put $d : = \gcd (a, b)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ), and suppose $d \neq 0$ , equivalently $(a, b) \neq (0, 0)$ . Since $d ∣ a$ and $d ∣ b$ , there are unique integers, written $a / d$ and $b / d$ , with

$a = d \cdot (a / d), b = d \cdot (b / d),$

uniqueness holding because $d \neq 0$ and $Z$ has cancellation (The integers have no zero divisors; multiplicative cancellation). Then

$\gcd (a / d, b / d) = 1,$

that is, $a / d$ and $b / d$ are coprime (Coprime integers: $\gcd (a, b) = 1$ ).

Facts & Assumptions

Given: Integers $a, b$ with $(a, b) \neq (0, 0)$ , and $d : = \gcd (a, b)$ .

[L1]

$\gcd (u, v) \geq 1$ when $(u, v) \neq (0, 0)$ , $\gcd (0, 0) = 0$ , and $\gcd (u, v)$ is a common divisor of $u$ and $v$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L2]

$\gcd (c u, c v) = ∣ c ∣ \gcd (u, v)$ for all $c, u, v$ ( $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all integers $a, b, c$ , the identity holding at $c = 0$ and at $(a, b) = (0, 0)$ as well).

[L3]

If $x z = y z$ and $z \neq 0$ then $x = y$ (The integers have no zero divisors; multiplicative cancellation).

[L4]

$d ∣ u$ means $u = d q$ for some $q$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L5]

[L6]

$Z$ is a commutative ring with $x \cdot 1 = x$ (The integers form a commutative ring, Arithmetic on the integers); its order is total, antisymmetric and transitive (The integers form a totally ordered ring, Order on the integers).

[L7]

$u$ and $v$ are coprime exactly when $\gcd (u, v) = 1$ (Coprime integers: $\gcd (a, b) = 1$ ).

Proof

technique · direct

1.1

Since $(a, b) \neq (0, 0)$ we have $d \geq 1$ , so $d \neq 0$ and $d \geq 0$ , whence $∣ d ∣ = d$ .

L1L5L6

2.1

$d$ is a common divisor of $a$ and $b$ , so there are integers $a^{'}$ and $b^{'}$ with $a = d a^{'}$ and $b = d b^{'}$ ; each is unique, since $d a^{'} = d a^{''}$ with $d \neq 0$ gives $a^{'} = a^{''}$ by cancellation. Write $a^{'} = a / d$ and $b^{'} = b / d$ .

step 1.1L1L3L4L6

3.1

By [L2] applied with $c = d$ , $u = a^{'}$ and $v = b^{'}$ : $d = \gcd (a, b) = \gcd (d a^{'}, d b^{'}) = ∣ d ∣ \gcd (a^{'}, b^{'}) = d \gcd (a^{'}, b^{'})$ .

step 1.1step 2.1L2

4.1

Also $d = d \cdot 1$ , so $d \cdot \gcd (a^{'}, b^{'}) = d \cdot 1$ with $d \neq 0$ , and cancellation gives $\gcd (a^{'}, b^{'}) = 1$ : the integers $a / d$ and $b / d$ are coprime.

step 1.1step 3.1L3L6L7∎

Remarks

The hypothesis $d \neq 0$ is not a restriction in disguise. It fails only at $(a, b) = (0, 0)$ , where $a / d$ and $b / d$ are not defined at all, since division by $0$ determines nothing.
This is the standard "reduce a fraction to lowest terms" statement, proved without any fractions: $a / d$ is defined as the unique integer solving $a = d \cdot x$ , and lives in $Z$ throughout.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$

Definition

Let $a, b \in Z$ . An integer $m$ is a common multiple of $a$ and $b$ when $a ∣ m$ and $b ∣ m$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

Case $a \neq 0$ and $b \neq 0$ : a least positive common multiple exists. The integer $∣ a b ∣$ is a positive common multiple. It is a common multiple because $a ∣ a$ gives $a ∣ a b$ and hence $a ∣ ∣ a b ∣$ , the last step because $∣ a b ∣$ is $a b$ or $- a b$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ , The absolute value $∣ a ∣$ of an integer), and symmetrically for $b$ ; and it is positive because $a b \neq 0$ (The integers have no zero divisors; multiplicative cancellation), so $∣ a b ∣ \geq 0$ and $∣ a b ∣ \neq 0$ (Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ). Every positive common multiple is nonnegative, hence of the form $ι (k)$ for a unique $k \in N$ , where $ι : N \to Z$ is the embedding of The naturals embed in the integers; so the set

$T : = {k \in N : ι (k) is a positive common multiple of a and b}$

is a nonempty subset of $N$ and has a least element $k_{0}$ (The well-ordering principle). Since $ι$ preserves the order, $ι (k_{0})$ is then the least positive common multiple of $a$ and $b$ , and we define

$lcm (a, b) : = ι (k_{0}),$

the least positive common multiple. It is unique, greatest and least elements being unique by antisymmetry (The integers form a totally ordered ring, Order on the integers).

Case $a = 0$ or $b = 0$ : the only common multiple is $0$ . Say $a = 0$ . Then $a ∣ m$ reads $0 ∣ m$ , which holds exactly for $m = 0$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ); and $0$ is indeed a common multiple, since every integer divides $0$ . So there is no positive common multiple at all, and we set

$lcm (a, b) : = 0.$

This is not a free choice dressed as one: $0$ is the only common multiple of the pair, so any other value would name an integer that is not a common multiple.

With both cases together $lcm (a, b)$ is defined for every pair, and $lcm (a, b) \geq 0$ always.

Remarks

The two boundary values agree, but they have different standing. $\gcd (0, 0) = 0$ is a genuine convention, adopted in Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ because no greatest common divisor exists there; $lcm (a, b) = 0$ at a vanishing argument is not a convention at all, since $0$ is the only common multiple available. With the two together, $\gcd (a, b) lcm (a, b) = ∣ a b ∣$ holds at every pair without exception (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ ). At $a = 0$ that identity reads $\gcd (0, b) \cdot 0 = 0 = ∣ 0 \cdot b ∣$ , which is true for every $b$ .
"Least" is least in the order of $Z$ , among the positive common multiples. The stronger statement, that $lcm (a, b)$ divides every common multiple and not merely that it is smallest, is a theorem and is proved as the first half of Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ . It is that divisibility form, not the minimality, that later pages use.
Two arguments only. As with $\gcd$ , no least common multiple of a longer list is defined on this page, because nothing here needs one.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$

Statement

Let $a, b \in Z$ , and write $d = \gcd (a, b)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ) and $ℓ = lcm (a, b)$ (Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ). Then:

every common multiple of $a$ and $b$ is a multiple of $ℓ$ , that is, $ℓ ∣ m$ whenever $a ∣ m$ and $b ∣ m$ ;
$d \cdot ℓ = ∣ a b ∣$ .

Both hold for every pair, including the pairs with $a = 0$ or $b = 0$ , where the two sides of clause 2 are $0$ .

Facts & Assumptions

Given: Integers $a$ and $b$ , $d : = \gcd (a, b)$ and $ℓ : = lcm (a, b)$ .

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x \cdot 1 = x$ , $x \cdot 0 = 0$ , $x \cdot (- 1) = - x$ , multiplication distributes over addition, and every $x$ has an additive inverse, with $- (- x) = x$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

The order on $Z$ is total, antisymmetric and transitive; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

[L3]

For $a, b$ both nonzero, $ℓ$ is the least positive common multiple of $a$ and $b$ ; if $a = 0$ or $b = 0$ then the only common multiple is $0$ and $ℓ = 0$ (Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ).

[L4]

$d \geq 1$ when $(a, b) \neq (0, 0)$ , $\gcd (0, 0) = 0$ , and $d$ is a common divisor of $a$ and $b$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L5]

If $d \neq 0$ then $a = d a^{'}$ and $b = d b^{'}$ for unique integers $a^{'} = a / d$ , $b^{'} = b / d$ , and $\gcd (a^{'}, b^{'}) = 1$ (If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime).

[L6]

$\gcd (u, v) = \gcd (v, u)$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ ).

[L7]

If $\gcd (u, v) = 1$ and $u ∣ v w$ then $u ∣ w$ (If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ).

[L8]

Divisibility is reflexive and transitive; $u ∣ v$ implies $u ∣ v w$ , $- u ∣ v$ and $u ∣ - v$ ; and $d ∣ u$ means $u = d q$ for some $q$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L9]

If $u ∣ v$ and $v \neq 0$ then $∣ u ∣ \leq ∣ v ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

[L10]

$∣ x ∣ \geq 0$ ; $∣ x ∣ = 0$ exactly when $x = 0$ ; $∣ x ∣ = x$ when $x \geq 0$ ; $∣ x y ∣ = ∣ x ∣ ∣ y ∣$ ; and $x$ is $∣ x ∣$ or $- ∣ x ∣$ (The absolute value $∣ a ∣$ of an integer, Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L11]

A product of two nonzero integers is nonzero, and $x z = y z$ with $z \neq 0$ gives $x = y$ (The integers have no zero divisors; multiplicative cancellation).

Proof

technique · cases

1.1

Case $a = 0$ or $b = 0$ . Then $ℓ = 0$ and the only common multiple of $a$ and $b$ is $0$ , so clause 1 reads $0 ∣ 0$ , which holds. And $a b = 0$ , so $∣ a b ∣ = 0 = d \cdot 0 = d ℓ$ : clause 2 holds.

assume-case degenerateL1L3L8L10

1.2

Case $a \neq 0$ and $b \neq 0$ . Then $(a, b) \neq (0, 0)$ , so $d \geq 1$ ; in particular $d \neq 0$ and $d \geq 0$ , so $∣ d ∣ = d$ . Fix $a^{'}, b^{'}$ with $a = d a^{'}$ , $b = d b^{'}$ and $\gcd (a^{'}, b^{'}) = 1$ .

assume-case genericL2L4L5L10

2.1

In the case of step 1.2 put $M : = d ∣ a^{'} b^{'} ∣$ . Both $a^{'}$ and $b^{'}$ are nonzero, since $a = d a^{'} \neq 0$ and $b = d b^{'} \neq 0$ ; hence $a^{'} b^{'} \neq 0$ , so $∣ a^{'} b^{'} ∣ \geq 0$ and $∣ a^{'} b^{'} ∣ \neq 0$ , and $M \neq 0$ .

step 1.2L1L10L11

3.1

$M$ is a common multiple of $a$ and $b$ . Indeed $d a^{'} b^{'} = (d a^{'}) b^{'} = a b^{'}$ and $d a^{'} b^{'} = (d b^{'}) a^{'} = b a^{'}$ , so $a ∣ d a^{'} b^{'}$ and $b ∣ d a^{'} b^{'}$ ; and $M = d ∣ a^{'} b^{'} ∣$ equals $d a^{'} b^{'}$ or $- (d a^{'} b^{'})$ , since $∣ a^{'} b^{'} ∣$ is $a^{'} b^{'}$ or $- (a^{'} b^{'})$ . So $a ∣ M$ and $b ∣ M$ .

step 1.2step 2.1L1L8L10

3.2

$M > 0$ : $d \geq 1 > 0$ and $∣ a^{'} b^{'} ∣ \geq 0$ with $∣ a^{'} b^{'} ∣ \neq 0$ , so $∣ a^{'} b^{'} ∣ > 0$ and the product of two positives is positive.

step 1.2step 2.1L2L10

3.3

Every common multiple $m$ of $a$ and $b$ is a multiple of $M$ . Write $m = a s = d a^{'} s$ . From $b ∣ m$ , that is $d b^{'} ∣ d a^{'} s$ , we get $d a^{'} s = d b^{'} t$ for some $t$ , and cancelling $d \neq 0$ gives $a^{'} s = b^{'} t$ , so $b^{'} ∣ a^{'} s$ . Since $\gcd (b^{'}, a^{'}) = \gcd (a^{'}, b^{'}) = 1$ , [L7] gives $b^{'} ∣ s$ , say $s = b^{'} u$ ; then $m = d a^{'} b^{'} u$ , so $d a^{'} b^{'} ∣ m$ and hence $M ∣ m$ , because $M$ is $d a^{'} b^{'}$ or $- (d a^{'} b^{'})$ .

step 1.2step 2.1L1L6L7L8L10L11

4.1

$M = ℓ$ . By steps 3.1 and 3.2, $M$ is a positive common multiple. If $p$ is any positive common multiple, then $M ∣ p$ by step 3.3 and $p \neq 0$ , so $∣ M ∣ \leq ∣ p ∣$ by [L9], that is $M \leq p$ since both are positive. So $M$ is the least positive common multiple, which is $ℓ$ .

step 3.1step 3.2step 3.3L3L9L10

5.1

Clause 1 in this case now follows from step 3.3, since $ℓ = M$ .

step 3.3step 4.1

5.2

Clause 2 in this case: $d ℓ = d \cdot d ∣ a^{'} b^{'} ∣ = ∣ d ∣ ∣ d ∣ ∣ a^{'} ∣ ∣ b^{'} ∣ = ∣ d a^{'} ∣ ∣ d b^{'} ∣ = ∣ (d a^{'}) (d b^{'}) ∣ = ∣ a b ∣$ , using $∣ d ∣ = d$ and multiplicativity of the absolute value throughout.

step 1.2step 4.1L1L10

6.1

The two cases of steps 1.1 and 1.2 are exhaustive, so clauses 1 and 2 hold for every pair $a, b$ .

step 1.1step 5.1step 5.2cases-exhaustive∎

Remarks

Clause 1 is the clause later pages use. "Least positive common multiple" is how $lcm$ was defined, but the useful property is that it divides every common multiple, which is what identifies $a Z \cap b Z$ with $lcm (a, b) Z$ in $a Z + b Z = \gcd (a, b) Z$ and $a Z \cap b Z = lcm (a, b) Z$ ; equivalently, in $(Z, +)$ the subgroup generated by ${a, b}$ is $⟨ \gcd (a, b) ⟩$ and $⟨ a ⟩ \cap ⟨ b ⟩ = ⟨ lcm (a, b) ⟩$ .
The absolute value in clause 2 is not decorative. The unsigned form $\gcd (a, b) lcm (a, b) = a b$ is false, and $(- 2, 3)$ refutes it: the companion page records this as FALSE: For all integers $a$ and $b$ , $\gcd (a, b) \cdot lcm (a, b) = a b$ ↗.
Where coprimality enters. The only substantial step is step 3.3, which proves that every common multiple is a multiple of $M$ ; what it uses is that $a / d$ and $b / d$ are coprime (If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime) together with the coprime divisibility lemma (If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ). Without those the argument gives only that $M$ is a common multiple, not the least one.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Every subgroup of $(Z, +)$ is $⟨ n ⟩ = n Z$ for exactly one natural number $n$

Statement

Write $ι : N \to Z$ for the embedding of The naturals embed in the integers, and for $g \in Z$ put

$g Z : = {g k : k \in Z} .$

Then $(Z, +, 0)$ is an abelian group (Group and abelian group), $g Z$ is the cyclic subgroup $⟨ g ⟩$ generated by $g$ (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups) for every $g$ , and:

every subgroup $H \leq (Z, +)$ (Subgroup) equals $ι (n) Z = ⟨ ι (n) ⟩$ for exactly one natural number $n$ . When $H = {0}$ that natural number is $0$ ; otherwise it is the natural number whose image is the least positive element of $H$ .

In particular every subgroup of $(Z, +)$ is cyclic.

Facts & Assumptions

Given: The set $Z$ with the operations of Arithmetic on the integers, and $ι (k) = [(k, 0)]$ (The naturals embed in the integers).

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , $x \cdot 0 = 0$ , multiplication distributes over addition, and every $x$ has an additive inverse $- x$ , with $- (- x) = x$ and $(- x) y = - (x y)$ ; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L2]

[L3]

$ι$ is injective, preserves addition, multiplication and order, and its image is exactly the nonnegative integers; $ι (0) = 0$ , $ι (1) = 1$ (The naturals embed in the integers).

[L4]

On $N$ : $m < n$ if and only if $σ (m) \leq n$ (Discreteness: $σ (n)$ is the immediate successor); $1 = σ (0)$ (The natural numbers $N$ (von Neumann)); $0 \leq k$ for every $k$ (Order on the natural numbers); and every nonempty subset has a least element (The well-ordering principle).

[L5]

A group is a monoid in which every element is invertible; a subgroup is a subset containing the identity and closed under the operation and under inverses, and is itself a group under the restricted operation (Group and abelian group, Subgroup, One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$ ).

[L6]

For $g$ in a group, $⟨ g ⟩$ is the smallest subgroup containing $g$ , and $⟨ g ⟩ = {g^{x} : x \in Z}$ (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups, $⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian).

[L7]

Powers are defined by $g^{0} = e$ and $g^{σ (k)} = g^{k} \cdot g$ for $k \in N$ , this being the unique function on $N$ with those two properties, and $g^{x} = (g^{k})^{- 1}$ when $x < 0$ and $- x = ι (k)$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , The recursion theorem).

[L8]

For $a \in Z$ and $b > 0$ there are $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

Proof

technique · direct

1.1

$(Z, +, 0)$ is an abelian group: addition is an associative and commutative binary operation, $0$ is a two-sided identity, and every $x$ has the two-sided inverse $- x$ .

L1L5

1.2

In this group the power $g^{x}$ is the ring product $g x$ . For $x = ι (k)$ with $k \in N$ , the function $k \mapsto g ι (k)$ satisfies $g ι (0) = g \cdot 0 = 0$ and $g ι (σ (k)) = g (ι (k) + 1) = g ι (k) + g$ , which are exactly the two defining equations of $k \mapsto g^{k}$ written additively; by the uniqueness in [L7] the two functions agree. For $x < 0$ , writing $- x = ι (k)$ , we get $g^{x} = - (g^{k}) = - (g ι (k)) = g (- ι (k)) = g x$ .

L1L3L7

1.3

Discreteness: if $0 < x$ in $Z$ then $1 \leq x$ . Indeed $x \geq 0$ , so $x = ι (k)$ with $k \neq 0$ , hence $0 < k$ and $1 = σ (0) \leq k$ in $N$ ; applying $ι$ gives $1 \leq x$ .

L2L3L4

1.4

Existence, main case. Suppose $H \neq {0}$ and pick $h \in H$ with $h \neq 0$ . Then $- h \in H$ as well, and by totality one of $h$ , $- h$ is positive; so the set $P$ of positive elements of $H$ is nonempty.

L1L2L5

2.1

Hence $⟨ g ⟩ = {g^{x} : x \in Z} = {g k : k \in Z} = g Z$ for every $g \in Z$ ; in particular $g Z$ is a subgroup.

step 1.2L6

2.2

Every element of $P$ is nonnegative, hence of the form $ι (k)$ ; so $T : = {k \in N : ι (k) \in P}$ is a nonempty subset of $N$ . Let $k_{0}$ be its least element and put $n : = ι (k_{0}) \in P$ .

step 1.4L3L4choose

2.3

For $g > 0$ , $g$ is the least positive element of $g Z$ . Indeed $g = g \cdot 1 \in g Z$ and $g > 0$ ; and if $g k > 0$ then $k > 0$ , since $k = 0$ gives $g k = 0$ and $k < 0$ gives $0 < - k$ , hence $0 < g (- k) = - (g k)$ and so $g k < 0$ . Then $1 \leq k$ by step 1.3, so $0 \leq k - 1$ and $0 \leq g (k - 1) = g k - g$ , that is $g \leq g k$ .

step 1.3L1L2

3.1

Existence, trivial case. If $H = {0}$ then $H = 0 Z = ⟨ 0 ⟩ = ⟨ ι (0) ⟩$ , since $0 \cdot k = 0$ for every $k$ .

step 2.1L1L3

3.2

$n$ is the least element of $P$ : for $p \in P$ write $p = ι (k)$ with $k \in T$ ; then $k_{0} \leq k$ , and applying $ι$ , which preserves the order, gives $n \leq p$ .

step 2.2L3

3.3

$⟨ n ⟩ \subseteq H$ , since $n \in H$ and $⟨ n ⟩$ is the smallest subgroup containing $n$ .

step 2.2L6

3.4

Uniqueness. Suppose $ι (m) Z = ι (n) Z = H$ with $m, n \in N$ . If $ι (n) = 0$ then $H = {0}$ , so $ι (m) \in H$ forces $ι (m) = 0$ and hence $m = 0 = n$ by injectivity. Otherwise $ι (n) > 0$ , so $H \neq {0}$ and likewise $ι (m) > 0$ ; by step 2.3 both $ι (m)$ and $ι (n)$ are the least positive element of $H$ , hence equal, and $m = n$ by injectivity.

step 2.3L2L3

4.1

$H \subseteq n Z$ . Let $h \in H$ . Since $n > 0$ , [L8] gives $h = q n + r$ with $0 \leq r < n$ . Now $q n \in n Z = ⟨ n ⟩ \subseteq H$ by step 2.1 and step 3.3, so $r = h - q n \in H$ because $H$ is closed under inverses and under addition. If $r$ were positive it would lie in $P$ and satisfy $r < n$ , contradicting step 3.2 together with antisymmetry; so $r = 0$ and $h = q n \in n Z$ .

step 2.1step 3.2step 3.3L1L2L5L8

5.1

Combining, $H = n Z = ⟨ n ⟩$ with $n = ι (k_{0})$ , which with step 3.1 proves existence for every subgroup.

step 2.1step 3.1step 3.3step 4.1

6.1

Every subgroup of $(Z, +)$ is therefore $⟨ ι (n) ⟩ = ι (n) Z$ for exactly one $n \in N$ , and in particular is cyclic.

step 5.1step 3.4∎

Remarks

Why this is proved here rather than cited. The published example $n Z$ is a subgroup of $(Z, +)$ for every $n \in Z$ , and every subgroup of $(Z, +)$ has this form gives the same classification, but it lives on an examples page, and examples pages are leaves in the library's reading order: no later page may depend on an item homed there. The classification is therefore re-established on a spine, so that this page and later ones have a citable home for it. Neither is used in proving the other.

The two are not quite the same statement, and the difference is the whole reason this one is worded as it is. The example asserts that every subgroup is $n Z$ for some $n \geq 0$ , and adds that $n$ may be taken to be $0$ or the least positive element of $H$ ; it does not assert that no other $n \geq 0$ names the same subgroup. The statement above asserts exactly one, which is strictly stronger. The extra content is small — if $a Z = b Z$ with $a, b \geq 0$ then each of $a, b$ divides the other, so $a = b$ — but it is what the uses below actually need, and it is proved here rather than assumed to come with the example.

What it is used for below. Exactly one thing: the uniqueness of the nonnegative generator, which is what lets $a Z + b Z = \gcd (a, b) Z$ be read as an identification of subgroups rather than as an accident about two sets ( $a Z + b Z = \gcd (a, b) Z$ and $a Z \cap b Z = lcm (a, b) Z$ ; equivalently, in $(Z, +)$ the subgroup generated by ${a, b}$ is $⟨ \gcd (a, b) ⟩$ and $⟨ a ⟩ \cap ⟨ b ⟩ = ⟨ lcm (a, b) ⟩$ ).
The generator is a natural number, hence a set. $n Z$ above always means $ι (n) Z$ ; the natural number $n$ is not itself an element of $Z$ , and the embedding is written out wherever the distinction could matter.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

$a Z + b Z = \gcd (a, b) Z$ and $a Z \cap b Z = lcm (a, b) Z$ ; equivalently, in $(Z, +)$ the subgroup generated by ${a, b}$ is $⟨ \gcd (a, b) ⟩$ and $⟨ a ⟩ \cap ⟨ b ⟩ = ⟨ lcm (a, b) ⟩$

Statement

Let $a, b \in Z$ , and put

$g Z : = {g k : k \in Z}, a Z + b Z : = {a x + b y : x, y \in Z} .$

Then $a Z + b Z$ and $a Z \cap b Z$ are subgroups of $(Z, +)$ (Subgroup), and

$a Z + b Z = \gcd (a, b) Z, a Z \cap b Z = lcm (a, b) Z$

(Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ). Equivalently, in the group $(Z, +)$ ,

$⟨ {a, b} ⟩ = ⟨ \gcd (a, b) ⟩, ⟨ a ⟩ \cap ⟨ b ⟩ = ⟨ lcm (a, b) ⟩$

(The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups). Since $\gcd (a, b) \geq 0$ and $lcm (a, b) \geq 0$ , and every subgroup of $(Z, +)$ has exactly one nonnegative generator (Every subgroup of $(Z, +)$ is $⟨ n ⟩ = n Z$ for exactly one natural number $n$ ), these are identifications of subgroups by their canonical generator, not merely equalities of two sets that happen to coincide.

Facts & Assumptions

Given: Integers $a$ and $b$ ; $d : = \gcd (a, b)$ and $ℓ : = lcm (a, b)$ .

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , $x \cdot 0 = 0$ , multiplication distributes over addition, and every $x$ has an additive inverse; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L2]

$(Z, +, 0)$ is an abelian group; $g Z = ⟨ g ⟩$ is a subgroup for every $g$ ; and every subgroup equals $ι (n) Z$ for exactly one $n \in N$ (Every subgroup of $(Z, +)$ is $⟨ n ⟩ = n Z$ for exactly one natural number $n$ , Group and abelian group).

[L3]

A subgroup contains the identity and is closed under the operation and under inverses; a nonempty $S \subseteq Z$ with $x - y \in S$ for all $x, y \in S$ is a subgroup of $(Z, +)$ (Subgroup, One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$ ).

[L4]

$⟨ S ⟩$ is the smallest subgroup containing $S$ : it contains $S$ and is contained in every subgroup containing $S$ (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups).

[L5]

An intersection of subgroups is a subgroup (The intersection of a nonempty family of subgroups of $G$ is a subgroup of $G$ ).

[L6]

$u ∣ v$ means $v = u k$ for some $k \in Z$ ; equivalently $v \in u Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L7]

$\gcd (a, b) \geq 0$ and is a common divisor of $a$ and $b$ ; $\gcd (0, 0) = 0$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L8]

[L9]

$lcm (a, b) \geq 0$ and is a common multiple of $a$ and $b$ (Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ).

[L10]

Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ ).

[L11]

The image of $ι : N \to Z$ is exactly the set of nonnegative integers, so every $x \geq 0$ is $ι (n)$ for a unique $n \in N$ (The naturals embed in the integers).

Proof

technique · direct

1.1

$I : = a Z + b Z$ is a subgroup of $(Z, +)$ : it contains $0 = a \cdot 0 + b \cdot 0$ , so is nonempty, and for $a x + b y$ and $a x^{'} + b y^{'}$ in $I$ the difference is $a (x - x^{'}) + b (y - y^{'}) \in I$ by distributivity, so the one-step test applies.

L1L3

1.2

$I \subseteq d Z$ . Since $d$ is a common divisor, write $a = d a_{1}$ and $b = d b_{1}$ ; then $a x + b y = d (a_{1} x + b_{1} y) \in d Z$ for all $x, y$ .

L1L6L7

1.3

$d \in I$ . If $(a, b) \neq (0, 0)$ this is [L8]. If $(a, b) = (0, 0)$ then $d = 0 = a \cdot 0 + b \cdot 0 \in I$ . The two cases are exhaustive.

L1L7L8

1.4

$a Z \cap b Z$ is a subgroup by [L2] and [L5], and by [L6] it is exactly the set of common multiples of $a$ and $b$ : $m \in a Z$ says $a ∣ m$ , and $m \in b Z$ says $b ∣ m$ .

L2L5L6

2.1

$I = ⟨ {a, b} ⟩$ . It contains $a = a \cdot 1 + b \cdot 0$ and $b = a \cdot 0 + b \cdot 1$ , so $⟨ {a, b} ⟩ \subseteq I$ by [L4]. Conversely any subgroup $H$ containing $a$ and $b$ contains $⟨ a ⟩ = a Z$ and $⟨ b ⟩ = b Z$ by [L2] and [L4], hence contains $a x + b y$ for all $x, y$ by closure under the operation; taking $H = ⟨ {a, b} ⟩$ gives $I \subseteq ⟨ {a, b} ⟩$ .

step 1.1L1L2L3L4

2.2

Hence $d Z = ⟨ d ⟩ \subseteq I$ , because $I$ is a subgroup containing $d$ and $⟨ d ⟩$ is the smallest such. With step 1.2, $I = d Z$ .

step 1.1step 1.2step 1.3L2L4

2.3

$ℓ Z \subseteq a Z \cap b Z$ : $ℓ$ is a common multiple by [L9], so $ℓ$ lies in the subgroup $a Z \cap b Z$ , and $ℓ Z = ⟨ ℓ ⟩$ is the smallest subgroup containing $ℓ$ .

step 1.4L2L4L9

3.1

$a Z \cap b Z \subseteq ℓ Z$ : every common multiple $m$ satisfies $ℓ ∣ m$ by [L10], that is $m \in ℓ Z$ . With step 2.3, $a Z \cap b Z = ℓ Z$ .

step 1.4step 2.3L6L10

4.1

Both identities are proved, and in group-theoretic form they read $⟨ {a, b} ⟩ = I = d Z = ⟨ d ⟩$ by step 2.1 and step 2.2, and $⟨ a ⟩ \cap ⟨ b ⟩ = a Z \cap b Z = ℓ Z = ⟨ ℓ ⟩$ by step 3.1 and [L2].

step 2.1step 2.2step 3.1L2

5.1

Finally $d \geq 0$ and $ℓ \geq 0$ , so each is $ι (n)$ for a natural $n$ by [L11], and by [L2] a subgroup of $(Z, +)$ has exactly one such generator; hence $d$ and $ℓ$ are the canonical generators of the two subgroups, and the identities identify the subgroups and not merely the underlying sets.

step 4.1L2L7L9L11∎

Remarks

This is the seam between the arithmetic and the group theory of this page, and it is the concrete shadow of the statement that $Z$ is a principal ideal domain. Read from left to right, it says that the set of integer combinations of $a$ and $b$ is exactly the set of multiples of their greatest common divisor — which is Bézout's identity and the divisibility characterisation of $\gcd$ packed into one equation between subgroups.
The classification is used for one thing only. Both inclusions above come from Bézout and divisibility; Every subgroup of $(Z, +)$ is $⟨ n ⟩ = n Z$ for exactly one natural number $n$ is invoked in step 5.1, for the uniqueness of the nonnegative generator, and nowhere else.
Boundary pairs. At $(a, b) = (0, 0)$ the theorem reads ${0} + {0} = 0 Z = {0}$ and ${0} \cap {0} = 0 Z$ , using $\gcd (0, 0) = 0$ and $lcm (0, 0) = 0$ ; at $a = 0$ and $b \neq 0$ it reads ${0} + b Z = ∣ b ∣ Z$ and ${0} \cap b Z = {0}$ . Both are true as stated, and neither needed a separate clause.

5 · Examples, counterexamples and false statements

None yet.

Divisibility, Greatest Common Divisors and Bézout's Identity

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

The absolute value ∣a∣∣a∣ of an integer

Definition

Remarks

Absolute value in ZZ: ∣a∣≥0∣a∣≥0; ∣a∣=0∣a∣=0 exactly when a=0a=0; ∣−a∣=∣a∣∣−a∣=∣a∣; ∣ab∣=∣a∣ ∣b∣∣ab∣=∣a∣∣b∣; −∣a∣≤a≤∣a∣−∣a∣≤a≤∣a∣; and ∣a∣≤c∣a∣≤c exactly when −c≤a≤c−c≤a≤c

Statement

Facts & Assumptions

Proof

Remarks

Divisibility in ZZ: d∣ad∣a when a=dqa=dq for some integer qq

Definition

Remarks

Division with remainder for any nonzero divisor: for a∈Za∈Z and b≠0b=0 there are unique q,r∈Zq,r∈Z with a=qb+ra=qb+r and 0≤r<∣b∣0≤r<∣b∣

Statement

Facts & Assumptions

Proof

Remarks

Divisibility is reflexive and transitive on ZZ, and is linear: if d∣ad∣a and d∣bd∣b then d∣ax+byd∣ax+by for all integers x,yx,y; also d∣ad∣a implies d∣acd∣ac, −d∣a−d∣a and d∣−ad∣−a

Statement

Facts & Assumptions

Proof

Remarks

If d∣ad∣a and a≠0a=0 then d≠0d=0 and ∣d∣≤∣a∣∣d∣≤∣a∣; hence the set of divisors of a nonzero integer is bounded above by ∣a∣∣a∣

Statement

Facts & Assumptions

Proof

Remarks

(Z,⋅,1)(Z,⋅,1) is a commutative monoid whose group of units is {1,−1}{1,−1}; equivalently u∣1u∣1 holds exactly for u=1u=1 and u=−1u=−1

Statement

Facts & Assumptions

Proof

Remarks

Associates in ZZ: integers each of which divides the other

Definition

Remarks

For integers aa and bb the following are equivalent: a∣ba∣b and b∣ab∣a; b=uab=ua for a unit uu; ∣a∣=∣b∣∣a∣=∣b∣. Being associates is an equivalence relation whose class of aa is {a,−a}{a,−a}

Statement

Facts & Assumptions

Proof

Remarks

A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element

Statement

Facts & Assumptions

Proof

Remarks

Common divisor, and the greatest common divisor gcd⁡(a,b)gcd(a,b), with the convention gcd⁡(0,0):=0gcd(0,0):=0

Definition

Remarks

gcd⁡gcd is symmetric and unchanged by signs: gcd⁡(a,b)=gcd⁡(b,a)=gcd⁡(∣a∣,∣b∣)gcd(a,b)=gcd(b,a)=gcd(∣a∣,∣b∣); moreover gcd⁡(a,0)=∣a∣gcd(a,0)=∣a∣, gcd⁡(a,1)=1gcd(a,1)=1, gcd⁡(a,a)=∣a∣gcd(a,a)=∣a∣, and gcd⁡(a,b)≥1gcd(a,b)≥1 unless a=b=0a=b=0

Statement

Facts & Assumptions

Proof

Remarks

Bézout's identity: for integers a,ba,b not both zero, gcd⁡(a,b)gcd(a,b) is the least positive element of { ax+by:x,y∈Z }{ax+by:x,y∈Z}; in particular ax+by=gcd⁡(a,b)ax+by=gcd(a,b) has an integer solution

Statement

Facts & Assumptions

Proof

Remarks

Every common divisor of aa and bb divides gcd⁡(a,b)gcd(a,b); consequently d=gcd⁡(a,b)d=gcd(a,b) exactly when d≥0d≥0, d∣ad∣a, d∣bd∣b, and every common divisor of aa and bb divides dd — a characterisation that holds at (a,b)=(0,0)(a,b)=(0,0) as well

Statement

Facts & Assumptions

Proof

Remarks

If a=qb+ra=qb+r then a,ba,b and b,rb,r have exactly the same common divisors, so gcd⁡(a,b)=gcd⁡(b,r)gcd(a,b)=gcd(b,r)

Statement

Facts & Assumptions

Proof

Remarks

The Euclidean algorithm: for a∈Za∈Z and b>0b>0 the remainder descent from (a,b)(a,b) terminates, and the last nonzero remainder is gcd⁡(a,b)gcd(a,b)

Statement

Facts & Assumptions

Proof

Remarks

The extended Euclidean algorithm: the same descent produces integers x,yx,y with ax+by=gcd⁡(a,b)ax+by=gcd(a,b), so Bézout coefficients are computed and not merely shown to exist

Statement

Facts & Assumptions

The absolute value $∣ a ∣$ of an integer

Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$

Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$

Division with remainder for any nonzero divisor: for $a \in Z$ and $b \neq 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < ∣ b ∣$

Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$

If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$

$(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$

Associates in $Z$ : integers each of which divides the other

For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$

Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$

$\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$

Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution

Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well

If $a = q b + r$ then $a, b$ and $b, r$ have exactly the same common divisors, so $\gcd (a, b) = \gcd (b, r)$

The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$

The extended Euclidean algorithm: the same descent produces integers $x, y$ with $a x + b y = \gcd (a, b)$ , so Bézout coefficients are computed and not merely shown to exist

Coprime integers: $\gcd (a, b) = 1$

$a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$

If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$

$\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all integers $a, b, c$ , the identity holding at $c = 0$ and at $(a, b) = (0, 0)$ as well

If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime

Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$

Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$

Every subgroup of $(Z, +)$ is $⟨ n ⟩ = n Z$ for exactly one natural number $n$

$a Z + b Z = \gcd (a, b) Z$ and $a Z \cap b Z = lcm (a, b) Z$ ; equivalently, in $(Z, +)$ the subgroup generated by ${a, b}$ is $⟨ \gcd (a, b) ⟩$ and $⟨ a ⟩ \cap ⟨ b ⟩ = ⟨ lcm (a, b) ⟩$