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.

✓ 9 results · all verified · 5 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 and Greatest Common Divisors: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

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

$\gcd (1071, 462) = 21$ by the Euclidean algorithm, with the back-substitution giving $21 = 7 \cdot 462 - 3 \cdot 1071$

Example

The remainder descent 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)$ from $(1071, 462)$ is

$1071 = 2 \cdot 462 + 147, 462 = 3 \cdot 147 + 21, 147 = 7 \cdot 21 + 0,$

so the second coordinates are $462, 147, 21, 0$ : the descent stops after three divisions, the last nonzero remainder is $21$ , and

$\gcd (1071, 462) = 21.$

Reading the divisions backwards gives Bézout coefficients:

$21 = 462 - 3 \cdot 147 = 462 - 3 (1071 - 2 \cdot 462) = 7 \cdot 462 - 3 \cdot 1071,$

that is, $1071 \cdot (- 3) + 462 \cdot 7 = 21$ .

Numerals. For $k \in N$ the symbol $k$ written inside $Z$ means $ι (k)$ , where $ι : N \to Z$ is the embedding of The naturals embed in the integers. Since $ι$ is injective and preserves addition, multiplication and order, each numerical identity and inequality below is the image of the corresponding one in $N$ , checked there by the ordinary decimal arithmetic of $N$ .

Facts & Assumptions

Given: The integers $1071$ , $462$ , $147$ , $21$ and $0$ , with numerals read as above through $ι$ (The naturals embed in the integers, The integers as equivalence classes of pairs of naturals).

[L1]

$Z$ is a commutative ring, and its order is total, antisymmetric, transitive and compatible with addition (The integers form a commutative ring, Arithmetic on the integers, The integers form a totally ordered ring, Order on the integers).

[L2]

For $a \in Z$ and $b > 0$ there is exactly one pair $(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$ ).

[L3]

If $a = q b + r$ then $\gcd (a, b) = \gcd (b, 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)$ ).

[L4]

$\gcd (u, 0) = ∣ u ∣$ , and $∣ u ∣ = u$ for $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$ , Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L5]

The descent 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)$ from $(a, b)$ with $b > 0$ sends $(u, v)$ with $v > 0$ to $(v, u - q v)$ , where $q$ is the quotient of $u$ by $v$ ; it terminates at the least index $N$ with vanishing second coordinate, and the last nonzero remainder equals $\gcd (a, b)$ .

[L6]

For $(a, b) \neq (0, 0)$ the equation $a x + b y = \gcd (a, b)$ has an integer solution (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), and the extended descent computes one (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).

[L7]

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

Verification

technique · direct

1.1

The three divisions are correct and are the ones [L2] produces. First, $2 \cdot 462 = 924$ and $924 + 147 = 1071$ , with $0 \leq 147 < 462$ . Second, $3 \cdot 147 = 441$ and $441 + 21 = 462$ , with $0 \leq 21 < 147$ . Third, $7 \cdot 21 = 147$ and $147 + 0 = 147$ , with $0 \leq 0 < 21$ . In each line the remainder satisfies the constraint of [L2], so by the uniqueness there it is the remainder.

L1L2algebra

2.1

Applying [L3] to the three identities in turn gives $\gcd (1071, 462) = \gcd (462, 147) = \gcd (147, 21) = \gcd (21, 0)$ .

step 1.1L3

2.2

Back-substitution. From the second division, $21 = 462 - 3 \cdot 147$ ; from the first, $147 = 1071 - 2 \cdot 462$ . Substituting, $21 = 462 - 3 (1071 - 2 \cdot 462) = 462 + 6 \cdot 462 - 3 \cdot 1071 = 7 \cdot 462 - 3 \cdot 1071$ .

step 1.1L1algebra

3.1

$\gcd (21, 0) = ∣ 21 ∣ = 21$ , since $21 \geq 0$ . Hence $\gcd (1071, 462) = 21$ .

step 2.1L1L4

3.2

The result checks numerically: $7 \cdot 462 = 3234$ , $3 \cdot 1071 = 3213$ , and $3234 - 3213 = 21$ .

step 2.2algebra

4.1

In the language of [L5], the descent from $(1071, 462)$ is $(1071, 462) \mapsto (462, 147) \mapsto (147, 21) \mapsto (21, 0)$ , so the second coordinates are $462, 147, 21, 0$ ; the least index with vanishing second coordinate is $N = 3$ , the last nonzero remainder is $21$ , and it equals $\gcd (1071, 462)$ as [L5] asserts.

step 1.1step 3.1L5

4.2

So $1071 \cdot (- 3) + 462 \cdot 7 = 21 = \gcd (1071, 462)$ , an explicit instance of [L6] with $(x, y) = (- 3, 7)$ .

step 3.1step 2.2step 3.2L6

5.1

Finally $21 ∣ 1071$ and $21 ∣ 462$ directly: $21 \cdot 51 = 1071$ and $21 \cdot 22 = 462$ , so the value found is indeed a common divisor, as it must be.

step 3.1L7algebra∎

Remarks

Three divisions, and the count is exact for this pair only. Nothing here, and nothing on the companion page, proves a bound on the number of divisions in terms of the size of the inputs.
The back-substitution is not a second algorithm. It is the same descent read in reverse, and 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 performs it forwards, carrying the coefficient pairs alongside the remainders instead of recovering them afterwards.
The coefficients are not unique: $1071 \cdot 19 + 462 \cdot (- 44) = 21$ as well, and 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)$ describes the whole family.

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

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

Example

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 asserts that $a x + b y = \gcd (a, b)$ has a solution; it does not assert that the solution is unique, and it is not. For $a = 1071$ and $b = 462$ , where $\gcd (a, b) = 21$ ( $\gcd (1071, 462) = 21$ by the Euclidean algorithm, with the back-substitution giving $21 = 7 \cdot 462 - 3 \cdot 1071$ ),

$1071 \cdot (- 3) + 462 \cdot 7 = 21 and 1071 \cdot 19 + 462 \cdot (- 44) = 21.$

The general statement, for $a$ and $b$ both nonzero, is this. Put $d = \gcd (a, b)$ , $a^{'} = a / d$ and $b^{'} = b / d$ (If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime), and let $(x_{0}, y_{0})$ be any solution of $a x + b y = d$ . Then the solutions of that equation are exactly the pairs

$(x, y) = (x_{0} + t b^{'}, y_{0} - t a^{'}) = (x_{0} + t b / d, y_{0} - t a / d), t \in Z .$

For the pair above, $d = 21$ , $a^{'} = 51$ and $b^{'} = 22$ , and $t = 1$ carries $(- 3, 7)$ to $(19, - 44)$ .

Numerals. For $k \in N$ the symbol $k$ written inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers; every numerical identity below is the image of the corresponding identity in $N$ .

Facts & Assumptions

Given: Nonzero integers $a$ and $b$ , $d : = \gcd (a, b)$ , and a solution $(x_{0}, y_{0})$ of $a x + b y = d$ ; and, for the numerical part, $a = 1071$ , $b = 462$ , $d = 21$ .

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $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).

[L3]

If $d = \gcd (a, b) \neq 0$ then $a = d a^{'}$ and $b = d b^{'}$ for unique integers $a^{'} = a / d$ and $b^{'} = b / d$ , and $\gcd (a^{'}, b^{'}) = 1$ (If $d = \gcd (a, b)$ is nonzero then $a / d$ and $b / d$ are coprime, Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , Coprime integers: $\gcd (a, b) = 1$ ).

[L4]

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

[L5]

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

[L6]

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

[L7]

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

[L8]

$\gcd (1071, 462) = 21$ ( $\gcd (1071, 462) = 21$ by the Euclidean algorithm, with the back-substitution giving $21 = 7 \cdot 462 - 3 \cdot 1071$ ).

Verification

technique · direct

1.1

Since $a \neq 0$ and $b \neq 0$ we have $(a, b) \neq (0, 0)$ , so $d \geq 1$ and in particular $d \neq 0$ ; fix $a^{'}, b^{'}$ with $a = d a^{'}$ , $b = d b^{'}$ and $\gcd (a^{'}, b^{'}) = 1$ . Both $a^{'}$ and $b^{'}$ are nonzero, since $d a^{'} = a \neq 0$ and $d b^{'} = b \neq 0$ .

givenL1L3

2.1

Every pair of the stated form is a solution: for $t \in Z$ , $a (x_{0} + t b^{'}) + b (y_{0} - t a^{'}) = (a x_{0} + b y_{0}) + t (a b^{'} - b a^{'}) = d + t ((d a^{'}) b^{'} - (d b^{'}) a^{'}) = d + t \cdot 0 = d$ .

step 1.1givenL1

2.2

Conversely, let $(x, y)$ satisfy $a x + b y = d$ . Subtracting $a x_{0} + b y_{0} = d$ gives $a (x - x_{0}) = - b (y - y_{0})$ , that is $d a^{'} (x - x_{0}) = - d b^{'} (y - y_{0})$ ; cancelling $d \neq 0$ gives $a^{'} (x - x_{0}) = - b^{'} (y - y_{0})$ .

step 1.1givenL1L7

2.3

The numerical instance. Here $d = 21$ by [L8], and $21 \cdot 51 = 1071$ , $21 \cdot 22 = 462$ , so $a^{'} = 51$ and $b^{'} = 22$ . The pair $(- 3, 7)$ is a solution, since $1071 \cdot (- 3) + 462 \cdot 7 = - 3213 + 3234 = 21$ .

step 1.1L1L8algebra

3.1

Hence $b^{'} ∣ a^{'} (x - x_{0})$ , and $\gcd (b^{'}, a^{'}) = \gcd (a^{'}, b^{'}) = 1$ , so $b^{'} ∣ x - x_{0}$ by [L5]: write $x - x_{0} = t b^{'}$ for some $t \in Z$ .

step 2.2L4L5L6

4.1

Substituting into step 2.2, $a^{'} t b^{'} = - b^{'} (y - y_{0})$ ; cancelling $b^{'} \neq 0$ gives $a^{'} t = - (y - y_{0})$ , that is $y = y_{0} - t a^{'}$ . So $(x, y) = (x_{0} + t b^{'}, y_{0} - t a^{'})$ .

step 1.1step 2.2step 3.1L1L7

5.1

With step 2.1 this shows the solutions are exactly the pairs $(x_{0} + t b^{'}, y_{0} - t a^{'})$ , $t \in Z$ .

step 2.1step 4.1

6.1

Taking $t = 1$ in step 5.1 gives $(- 3 + 22, 7 - 51) = (19, - 44)$ , and directly $1071 \cdot 19 + 462 \cdot (- 44) = 20349 - 20328 = 21$ . So the same equation has at least the two solutions $(- 3, 7)$ and $(19, - 44)$ , and they are distinct because $- 3 \neq 19$ .

step 5.1step 2.3L1algebra∎

Remarks

The family is infinite. Distinct values of $t$ give distinct pairs, since $b^{'} \neq 0$ and $x_{0} + t b^{'} = x_{0} + t^{'} b^{'}$ forces $t = t^{'}$ by cancellation. So a Bézout equation with $a, b$ both nonzero never has a unique solution.
Why the statement is restricted to $a, b$ both nonzero. With $b = 0$ and $a \neq 0$ the quotient $b / d$ is $0$ and the family collapses to $(x_{0}, y_{0} - t a / d)$ , which is still the complete solution set but for a different reason: $x$ is then forced and $y$ is free. The uniform statement above is the one used elsewhere, and the degenerate case is recorded here so that its absence from the claim is deliberate rather than an oversight.

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item 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$

Example

The two boundary values of $\gcd$ are

$\gcd (a, 0) = ∣ a ∣ for every a, \gcd (0, 0) = 0,$

the first 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$ and the second by the convention fixed in Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ . The point of this example is that the second is not free: instantiating the scaling identity $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ of $\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 at $c = 0$ gives

$\gcd (0, 0) = \gcd (0 \cdot a, 0 \cdot b) = ∣ 0 ∣ \gcd (a, b) = 0,$

so $0$ is the only value the identity permits. The same conclusion follows from the identity taken at $(a, b) = (0, 0)$ with $c = 1 + 1$ : it reads $\gcd (0, 0) = (1 + 1) \gcd (0, 0)$ , and an integer $g$ with $g = g + g$ is $0$ .

Facts & Assumptions

Given: Integers $a, b, c$ .

[L1]

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

[L3]

$\gcd (u, 0) = ∣ u ∣$ for every $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$ ).

[L4]

$\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 $\gcd (u, v) \geq 0$ always.

[L5]

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

[L6]

$∣ 0 ∣ = 0$ , and $∣ u ∣ = u$ for $u \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$ ).

[L7]

Every integer divides $0$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ), and 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).

[L8]

The embedding $ι : N \to Z$ has image exactly the nonnegative integers, and $ι (1) = 1$ , $ι (1 + 1) = 1 + 1$ since $ι$ preserves addition (The naturals embed in the integers, The integers as equivalence classes of pairs of naturals).

Verification

technique · direct

1.1

$\gcd (a, 0) = ∣ a ∣$ for every $a$ , by [L3]; at $a = 0$ this reads $\gcd (0, 0) = ∣ 0 ∣ = 0$ , agreeing with the convention.

L3L4L6

1.2

Instantiate [L5] at $c = 0$ : $\gcd (0 \cdot a, 0 \cdot b) = ∣ 0 ∣ \gcd (a, b)$ . The left side is $\gcd (0, 0)$ and the right side is $0 \cdot \gcd (a, b) = 0$ , so $\gcd (0, 0) = 0$ .

L1L5L6

1.3

Instantiate [L5] at $(a, b) = (0, 0)$ and $c = 1 + 1$ : writing $g : = \gcd (0, 0)$ , it reads $g = ∣ 1 + 1 ∣ g$ .

2.1

An integer $g$ satisfying $g = (1 + 1) g = g + g$ is $0$ : adding $- g$ to both sides gives $0 = g$ . Combined with step 1.3, and with $∣ 1 + 1 ∣ = 1 + 1$ because $1 + 1 = ι (1 + 1)$ is nonnegative, this is a second derivation of $\gcd (0, 0) = 0$ .

step 1.3L1L4L6L8

3.1

So the value $0$ is not chosen but determined, once the scaling identity is required to hold at every triple: steps 1.2 and 2.1 each force it, and step 1.1 shows it agrees with $\gcd (a, 0) = ∣ a ∣$ read at $a = 0$ .

step 1.1step 1.2step 2.1

4.1

The divisibility reading agrees as well: every integer divides $0$ , so every common divisor of $(0, 0)$ divides $0$ , and $0$ is a common divisor of $(0, 0)$ that is nonnegative — which is exactly the characterisation of $\gcd$ in [L7], returning the value $0$ .

L4L7∎

Remarks

What goes wrong without a convention is not that some identity becomes awkward but that $\gcd (0, 0)$ names nothing at all: the common divisors of $(0, 0)$ are all of $Z$ and 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).
$\gcd (a, 0) = ∣ a ∣$ is where the absolute value earns its place. Without it the natural guess $\gcd (a, 0) = a$ would be negative for negative $a$ , and $\gcd$ would fail to be nonnegative.

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item 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

Example

For integers $a, b, c$ , the equation

$a x + b y = c$

has a solution $(x, y) \in Z \times Z$ if and only if $\gcd (a, b) ∣ c$ (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$ ).

With $a = 6$ and $b = 15$ , where $\gcd (6, 15) = 3$ :

$6 x + 15 y = 9$ is solvable, since $3 ∣ 9$ ; explicitly $6 \cdot (- 1) + 15 \cdot 1 = 9$ ;
$6 x + 15 y = 7$ has no solution, since $3 ∤ 7$ : dividing, $7 = 2 \cdot 3 + 1$ with remainder $1 \neq 0$ .

Numerals. For $k \in N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers; the numerical identities below are the images of the corresponding identities in $N$ .

Facts & Assumptions

Given: Integers $a, b, c$ , and $g : = \gcd (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 (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 (The integers form a totally ordered ring, Order on the integers).

[L3]

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

[L4]

For $(a, b) \neq (0, 0)$ there are $x_{0}, y_{0}$ 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).

[L5]

$d = \gcd (u, v)$ exactly when $d \geq 0$ , $d ∣ u$ , $d ∣ v$ and every common divisor of $u$ and $v$ 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).

[L6]

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

[L7]

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

[L8]

For $u \in Z$ and $v > 0$ there is exactly one pair $(q, r)$ with $u = q v + r$ and $0 \leq r < v$ , and $v ∣ u$ holds exactly when $r = 0$ (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$ ).

Verification

technique · direct

1.1

If $a x + b y = c$ has a solution, then $g ∣ a$ and $g ∣ b$ give $g ∣ a x + b y = c$ by [L6].

L3L6

1.2

Conversely suppose $g ∣ c$ , say $c = g k$ . If $(a, b) \neq (0, 0)$ , take $x_{0}, y_{0}$ with $a x_{0} + b y_{0} = g$ and multiply by $k$ : $a (x_{0} k) + b (y_{0} k) = g k = c$ , a solution.

L1L4L7

1.3

If instead $(a, b) = (0, 0)$ then $g = 0$ , so $0 ∣ c$ forces $c = 0$ , and $a \cdot 0 + b \cdot 0 = 0 = c$ is a solution. The two cases are exhaustive.

L1L3L7

1.4

$\gcd (6, 15) = 3$ . Indeed $3 \geq 0$ ; $6 = 3 \cdot 2$ and $15 = 3 \cdot 5$ , so $3 ∣ 6$ and $3 ∣ 15$ ; and $6 \cdot (- 2) + 15 \cdot 1 = - 12 + 15 = 3$ , so every common divisor of $6$ and $15$ divides $3$ by [L6]. By [L5] this is exactly the characterisation of $\gcd (6, 15)$ .

L1L5L6L7algebra

2.1

So solvability of $a x + b y = c$ is equivalent to $g ∣ c$ .

step 1.1step 1.2step 1.3

3.1

$3 ∣ 9$ , since $9 = 3 \cdot 3$ ; so $6 x + 15 y = 9$ is solvable by step 2.1, and $6 \cdot (- 1) + 15 \cdot 1 = - 6 + 15 = 9$ exhibits a solution.

step 2.1step 1.4L1L7algebra

4.1

$3 ∤ 7$ : since $3 > 0$ , [L8] applies, and $7 = 2 \cdot 3 + 1$ with $0 \leq 1 < 3$ is the unique such representation, so the remainder is $1 \neq 0$ and $3$ does not divide $7$ . Hence $6 x + 15 y = 7$ has no integer solution by step 2.1.

step 2.1step 1.4L1L2L8algebra∎

Remarks

The criterion is decidable by the Euclidean algorithm: compute $\gcd (a, b)$ by 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)$ , test whether it divides $c$ by division with remainder, and, when it does, obtain a solution by scaling the Bézout pair that 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 computes.
Solutions are never unique when $a$ and $b$ are both nonzero; the family is described in 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)$ , and scaling that description by $k = c / \gcd (a, b)$ describes the solutions of $a x + b y = c$ .
The unsolvable case is genuinely unsolvable, not merely hard. Every value of $6 x + 15 y$ is a multiple of $3$ , and $7$ is not one; no search is involved.

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

$12 Z + 18 Z = 6 Z$ and $12 Z \cap 18 Z = 36 Z$ , the arithmetic of $\gcd$ and $lcm$ read off the subgroups of $(Z, +)$

Example

Take $a = 12$ and $b = 18$ . Then $\gcd (12, 18) = 6$ and $lcm (12, 18) = 36$ , and $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) ⟩$ turns these two numbers into two statements about subgroups of $(Z, +)$ :

$12 Z + 18 Z = 6 Z, 12 Z \cap 18 Z = 36 Z .$

The first says that the integers expressible as $12 x + 18 y$ are exactly the multiples of $6$ ; the smallest positive one is $6 = 12 \cdot (- 1) + 18 \cdot 1$ . The second says that the integers divisible by both $12$ and $18$ are exactly the multiples of $36$ . The product check is $\gcd \cdot lcm = 6 \cdot 36 = 216 = ∣ 12 \cdot 18 ∣$ .

Numerals. For $k \in N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers.

Facts & Assumptions

Given: The integers $12$ , $18$ , $6$ , $36$ and $216$ , and $g Z = {g k : k \in Z}$ .

[L1]

$Z$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , $x \cdot (- 1) = - x$ , and multiplication distributes over addition (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L2]

[L3]

[L4]

$\gcd (u, v) lcm (u, v) = ∣ u v ∣$ , and every common multiple of $u$ and $v$ is a multiple of $lcm (u, v)$ (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ , Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ).

[L5]

$∣ x ∣ = x$ for $x \geq 0$ , and $∣ x y ∣ = ∣ x ∣ ∣ y ∣$ (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$ ).

[L6]

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

[L7]

$a Z + b Z = \gcd (a, b) Z$ and $a Z \cap b Z = lcm (a, b) Z$ , and these are subgroups of $(Z, +)$ ( $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) ⟩$ , Subgroup, Group and abelian group, The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups).

[L8]

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

Verification

technique · direct

1.1

$\gcd (12, 18) = 6$ . Indeed $6 \geq 0$ ; $12 = 6 \cdot 2$ and $18 = 6 \cdot 3$ , so $6 ∣ 12$ and $6 ∣ 18$ ; and $12 \cdot (- 1) + 18 \cdot 1 = - 12 + 18 = 6$ , so every common divisor of $12$ and $18$ divides $6$ by [L3]. By [L2] this characterises $\gcd (12, 18)$ .

L1L2L3algebra

2.1

$lcm (12, 18) = 36$ . By [L4], $\gcd (12, 18) lcm (12, 18) = ∣ 12 \cdot 18 ∣ = ∣ 216 ∣ = 216$ ; with step 1.1 this reads $6 \cdot lcm (12, 18) = 216$ . Since $6 \cdot 36 = 216$ and $6 \neq 0$ , cancellation gives $lcm (12, 18) = 36$ .

step 1.1L1L4L5L6algebra

3.1

Applying [L7] with $a = 12$ and $b = 18$ : $12 Z + 18 Z = \gcd (12, 18) Z = 6 Z$ and $12 Z \cap 18 Z = lcm (12, 18) Z = 36 Z$ .

step 1.1step 2.1L7

4.1

Both right-hand sides are written with their canonical generator: $6 \geq 0$ and $36 \geq 0$ , and by [L8] no other nonnegative integer generates the same subgroup, so the two identities pin the subgroups down rather than merely exhibiting one description of each.

step 3.1L8

5.1

The two statements read concretely: an integer is of the form $12 x + 18 y$ exactly when it is a multiple of $6$ — with $6 = 12 \cdot (- 1) + 18 \cdot 1$ the smallest positive such value — and an integer is divisible by both $12$ and $18$ exactly when it is a multiple of $36$ , which is the divisibility clause of [L4] instantiated here.

step 1.1step 3.1L3L4∎

Remarks

The example is the seam in miniature. On the left of each identity is a construction in the group $(Z, +)$ — a sum of subgroups, an intersection of subgroups — and on the right is a number computed by arithmetic. $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 what makes the two sides the same object.
$36 = 12 \cdot 3 = 18 \cdot 2$ , so $36$ is visibly a common multiple; what is not visible without the theorem is that every common multiple is a multiple of it, which is why $12 Z \cap 18 Z$ is exactly $36 Z$ and not merely contains it.

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

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

Example

The sequence. Write $k + 1$ for $σ (k)$ and $k + 2$ for $σ (σ (k))$ (Addition of natural numbers). By the recursion theorem (The recursion theorem) applied to the set $Z \times Z$ , the element $(0, 1)$ and the function $(u, v) \mapsto (v, u + v)$ , there is exactly one $G : N \to Z \times Z$ with $G (0) = (0, 1)$ and $G (k + 1) = (v, u + v)$ whenever $G (k) = (u, v)$ . Define $F_{k}$ to be the first coordinate of $G (k)$ . Then $G (k) = (F_{k}, F_{k + 1})$ for every $k$ , so

$F_{0} = 0, F_{1} = 1, F_{k + 2} = F_{k + 1} + F_{k},$

and the sequence begins $0, 1, 1, 2, 3, 5, 8, 13$ . The indexing starts at $F_{0} = 0$ , and the statements below depend on that choice.

Coprimality. For every $k \in N$ ,

$\gcd (F_{k + 1}, F_{k}) = 1,$

so consecutive Fibonacci numbers are coprime (Coprime integers: $\gcd (a, b) = 1$ ).

The division count. For $m \in N$ let $R$ be the remainder descent 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)$ from $(F_{m + 3}, F_{m + 2})$ , which is legitimate because $F_{m + 2} > 0$ , and for $k$ below the terminating index $N$ let $q_{k}$ be the quotient used at step $k$ , so that $a_{k} = q_{k} b_{k} + b_{k + 1}$ with $0 \leq b_{k + 1} < b_{k}$ . Then

$N = m + 1, q_{k} = 1 for k < m, q_{m} = 2.$

Equivalently, on $(F_{n + 2}, F_{n + 1})$ with $n = m + 1 \geq 1$ the algorithm performs exactly $n$ divisions. At $m = 0$ the pair is $(F_{3}, F_{2}) = (2, 1)$ , there is a single division $2 = 2 \cdot 1 + 0$ , and the list of quotients equal to $1$ is empty.

What is not claimed. Nothing here says these pairs are the worst case for their size; that is Lamé's theorem, and no bound on the number of divisions in terms of the size of the inputs is available at this point in the reading order.

Facts & Assumptions

Given: The sequence $F : N \to Z$ described above, with $F_{0} = 0$ , $F_{1} = 1$ and $F_{k + 2} = F_{k + 1} + F_{k}$ .

[L1]

$Z$ is a commutative ring; its order is total, antisymmetric and transitive and is compatible with addition; positives are closed under multiplication; $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]

Induction on $N$ (The principle of mathematical induction); $σ (k) = k + 1$ (Addition of natural numbers, The natural numbers $N$ (von Neumann)); $m < n$ iff $σ (m) \leq n$ on $N$ (Discreteness: $σ (n)$ is the immediate successor, Order on the natural numbers).

[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).

[L4]

$ι : N \to Z$ is injective, preserves order, and has image the nonnegative integers (The naturals embed in the integers); hence $0 < x$ in $Z$ implies $1 \leq x$ , since $x = ι (k)$ with $k \neq 0$ , so $σ (0) \leq k$ by the discreteness of [L2] and order preservation gives $1 = ι (1) \leq ι (k) = x$ (Discreteness: $σ (n)$ is the immediate successor).

[L5]

For $u \in Z$ and $v > 0$ there is exactly one pair $(q, r)$ 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$ ).

[L6]

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

[L7]

$\gcd (u, 0) = ∣ u ∣$ and $∣ u ∣ = u$ for $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$ , Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L8]

The descent 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)$ from $(a, b)$ with $b > 0$ satisfies $R (0) = (a, b)$ and $R (k + 1) = (b_{k}, a_{k} - q_{k} b_{k})$ whenever $b_{k} > 0$ , with $q_{k}$ the quotient of $a_{k}$ by $b_{k}$ ; it is the unique such sequence, and $N$ is the least index with $b_{N} = 0$ .

[L9]

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

Verification

technique · induction

1.1

$G (k) = (F_{k}, F_{k + 1})$ for every $k$ , by induction: it holds at $k = 0$ since $G (0) = (0, 1) = (F_{0}, F_{1})$ , and if $G (k) = (F_{k}, F_{k + 1})$ then $G (k + 1) = (F_{k + 1}, F_{k} + F_{k + 1})$ , whose first coordinate is $F_{k + 1}$ , so the second is $F_{k + 2}$ by definition of $F$ as the first coordinate one step later. Hence $F_{k + 2} = F_{k + 1} + F_{k}$ .

L1L2L3

1.2

Induction hypothesis: fix $m$ and assume that the descent from $(F_{m + 3}, F_{m + 2})$ terminates at index $m + 1$ with quotients $q_{k} = 1$ for $k < m$ and $q_{m} = 2$ .

2.1

For every $k$ : $F_{k} \geq 0$ and $F_{k + 1} \geq 1$ . By induction, at $k = 0$ this is $F_{0} = 0 \geq 0$ and $F_{1} = 1 \geq 1$ ; and if it holds at $k$ then $F_{k + 1} \geq 1 \geq 0$ and $F_{k + 2} = F_{k + 1} + F_{k} \geq 1 + 0 = 1$ , using compatibility of the order with addition.

step 1.1L1L2L4

2.2

Coprimality. By induction on $k$ : at $k = 0$ , $\gcd (F_{1}, F_{0}) = \gcd (1, 0) = ∣ 1 ∣ = 1$ by [L7]. If $\gcd (F_{k + 1}, F_{k}) = 1$ , then $F_{k + 2} = 1 \cdot F_{k + 1} + F_{k}$ and [L6] give $\gcd (F_{k + 2}, F_{k + 1}) = \gcd (F_{k + 1}, F_{k}) = 1$ . So $\gcd (F_{k + 1}, F_{k}) = 1$ for every $k$ , and consecutive Fibonacci numbers are coprime.

step 1.1L1L2L6L7L9

2.3

Base case of the division count, $m = 0$ . Here $F_{2} = F_{1} + F_{0} = 1$ and $F_{3} = F_{2} + F_{1} = 1 + 1 = 2$ , so the descent starts at $(2, 1)$ with $b_{0} = 1 > 0$ . Dividing, $2 = q \cdot 1 + r$ with $0 \leq r < 1$ forces $r = 0$ , since $0 < r$ would give $1 \leq r$ by [L4]; hence $q = 2$ and $R (1) = (1, 0)$ . So $N = 1 = m + 1$ , the single quotient is $q_{0} = 2$ , and there is no index $k < m = 0$ .

basestep 1.1L1L4L5L8

3.1

For every $m$ : $0 \leq F_{m + 1}$ , $0 < F_{m + 2}$ and $F_{m + 2} < F_{m + 3}$ . The first two are step 2.1; and $F_{m + 3} = F_{m + 2} + F_{m + 1}$ with $F_{m + 1} \geq 1 > 0$ gives $F_{m + 2} < F_{m + 3}$ .

step 1.1step 2.1L1

4.1

Inductive step. Consider the descent $R^{'}$ from $(F_{m + 4}, F_{m + 3})$ ; it is legitimate since $F_{m + 3} > 0$ by step 3.1. Its first division is $F_{m + 4} = 1 \cdot F_{m + 3} + F_{m + 2}$ , and $0 \leq F_{m + 2} < F_{m + 3}$ by step 3.1, so by the uniqueness in [L5] the quotient is $q_{0}^{'} = 1$ and $R^{'} (1) = (F_{m + 3}, F_{m + 2})$ .

step 1.1step 3.1L5L8

5.1

The shifted sequence $k \mapsto R^{'} (k + 1)$ starts at $(F_{m + 3}, F_{m + 2})$ and obeys the same recursion as $R^{'}$ , hence, by the uniqueness in [L3], equals the descent from $(F_{m + 3}, F_{m + 2})$ . Therefore its terminating index is $m + 1$ by step 1.2, so $R^{'}$ terminates at index $1 + (m + 1) = (m + 1) + 1$ ; and its quotients are $q_{0}^{'} = 1$ followed by the quotients of step 1.2, that is $1$ repeated $m + 1$ times and then $2$ . This is the claim at $m + 1$ .

step 1.2step 4.1L3L8

6.1

By induction the division count holds for every $m \in N$ : the descent from $(F_{m + 3}, F_{m + 2})$ takes exactly $m + 1$ divisions, with quotient $1$ in the first $m$ and quotient $2$ in the last; together with step 2.2 this is the whole example.

step 2.2step 2.3step 5.1L2discharge-induction∎

Remarks

The last quotient is $2$ , not $1$ , and the reason is the repeated value $F_{1} = F_{2} = 1$ . The chain of quotient- $1$ divisions $F_{k + 2} = 1 \cdot F_{k + 1} + F_{k}$ is a valid division only while $F_{k} < F_{k + 1}$ , which fails exactly at $k = 1$ . The descent therefore ends at the pair $(F_{3}, F_{2}) = (2, 1)$ with the single division $2 = 2 \cdot 1 + 0$ . A statement of the form "quotient $1$ at every step" is false for that reason, and the count would also be wrong at the first index if the sequence were indexed from $1$ .
Coprimality does not need the division count, and the count does not need coprimality; they are recorded together because both are read off the same identity $F_{k + 2} = F_{k + 1} + F_{k}$ , once through If $a = q b + r$ then $a, b$ and $b, r$ have exactly the same common divisors, so $\gcd (a, b) = \gcd (b, r)$ and once through 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$ .
No worst-case claim. Lamé's theorem — that the Fibonacci pairs minimise the size of the inputs for a given number of divisions — is a genuinely different statement, and nothing above establishes or assumes it.

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

$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

Statement refuted

Refuted claim: for all integers $d, a, b$ , if $d ∣ a b$ then $d ∣ a$ or $d ∣ b$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

Witness: $d = 6$ , $a = 4$ , $b = 9$ . Here $4 \cdot 9 = 36 = 6 \cdot 6$ , so $6 ∣ 4 \cdot 9$ ; but $4 = 0 \cdot 6 + 4$ and $9 = 1 \cdot 6 + 3$ have nonzero remainders, so $6 ∤ 4$ and $6 ∤ 9$ .

The true statement in this direction carries a coprimality hypothesis (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$ ): if $\gcd (d, a) = 1$ and $d ∣ a b$ then $d ∣ b$ . That hypothesis is exactly what fails here, in both readings: $\gcd (6, 4) = 2$ and $\gcd (6, 9) = 3$ , and neither is $1$ .

Numerals. For $k \in N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers.

Facts & Assumptions

Given: The integers $4$ , $6$ , $9$ and $36$ .

[L1]

$Z$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , $x \cdot (- 1) = - x$ , $x \cdot 0 = 0$ , and multiplication distributes over addition (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 (The integers form a totally ordered ring, Order on the integers).

[L3]

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

[L4]

[L5]

$d = \gcd (u, v)$ exactly when $d \geq 0$ , $d ∣ u$ , $d ∣ v$ , and every common divisor of $u$ and $v$ 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, Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L6]

[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$ ); $u$ and $v$ are coprime exactly when $\gcd (u, v) = 1$ (Coprime integers: $\gcd (a, b) = 1$ ).

[L8]

$ι$ is injective and preserves order, and $2 \neq 1$ , $3 \neq 1$ in $N$ (The naturals embed in the integers).

Counterexample

technique · direct

1.1

$4 \cdot 9 = 36$ and $36 = 6 \cdot 6$ , so $6 ∣ 4 \cdot 9$ .

L1L3algebra

1.2

$6 ∤ 4$ : since $6 > 0$ , [L4] applies, and $4 = 0 \cdot 6 + 4$ with $0 \leq 4 < 6$ is the unique representation of that form, so the remainder is $4 \neq 0$ .

L1L2L4algebra

1.3

$6 ∤ 9$ : likewise $9 = 1 \cdot 6 + 3$ with $0 \leq 3 < 6$ , so the remainder is $3 \neq 0$ .

L1L2L4algebra

1.4

$\gcd (6, 4) = 2$ : indeed $2 \geq 0$ , $6 = 2 \cdot 3$ and $4 = 2 \cdot 2$ , so $2$ is a common divisor; and $6 \cdot 1 + 4 \cdot (- 1) = 6 - 4 = 2$ , so every common divisor of $6$ and $4$ divides $2$ by [L6]. By [L5], $\gcd (6, 4) = 2$ , and $2 \neq 1$ by [L8].

L1L5L6L8algebra

1.5

$\gcd (6, 9) = 3$ : indeed $3 \geq 0$ , $6 = 3 \cdot 2$ and $9 = 3 \cdot 3$ ; and $6 \cdot (- 1) + 9 \cdot 1 = 3$ , so every common divisor divides $3$ by [L6]. By [L5], $\gcd (6, 9) = 3$ , and $3 \neq 1$ by [L8].

L1L5L6L8algebra

2.1

Steps 1.1, 1.2 and 1.3 exhibit $d = 6$ , $a = 4$ , $b = 9$ with $d ∣ a b$ , $d ∤ a$ and $d ∤ b$ : the claim is refuted.

step 1.1step 1.2step 1.3

3.1

So [L7] is not contradicted: applied with $u = 6$ it would need $\gcd (6, 4) = 1$ or $\gcd (6, 9) = 1$ , and by steps 1.4 and 1.5 neither holds. The failure of the refuted claim is exactly the failure of coprimality, not a failure of the lemma.

step 2.1step 1.4step 1.5L7∎

Remarks

This is the gap that primality closes. When $d$ is prime its only positive divisors are $1$ and itself, so $\gcd (d, a) = 1$ for every $a$ that $d$ does not divide, and the refuted claim becomes true. Primes are not defined on this page, and the statement above is not repaired here; it is recorded so that the coprimality hypothesis of 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 visibly doing work rather than decorating the statement.
The witness is minimal in spirit, not proved minimal. No claim is made that $(6, 4, 9)$ is the smallest such triple.

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

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

Statement refuted

Refuted claim: for every pair of integers $(a, b)$ the set

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

of common divisors has a greatest element, so that $\gcd (a, b)$ can be defined as that maximum at every pair (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

Witness: $(a, b) = (0, 0)$ . Every integer divides $0$ , so $D (0, 0) = Z$ ; and $Z$ has no greatest element, since $m < m + 1$ for every $m$ . So there is no maximum to take, and $\gcd (0, 0)$ is fixed by the convention $\gcd (0, 0) : = 0$ of Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ rather than computed.

This does not contradict A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element: that lemma requires the set to be bounded above, and $Z$ is not.

Facts & Assumptions

Given: The set $D (0, 0)$ of common divisors of $0$ and $0$ .

[L1]

$Z$ is a commutative ring: $x \cdot 0 = 0$ , $x + 0 = x$ , $x \cdot 1 = x$ , $x \cdot (- 1) = - x$ , and every $x$ has an additive inverse (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; 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]

$d ∣ u$ means $u = d q$ for some $q$ ; in particular $d ∣ 0$ for every $d$ , since $0 = d \cdot 0$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L4]

A nonempty set of integers bounded above has a 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).

[L5]

$ι : N \to Z$ is injective with image the nonnegative integers, and $ι (1) = 1$ , $ι (0) = 0$ (The naturals embed in the integers).

[L6]

Counterexample

technique · direct

1.1

$D (0, 0) = Z$ : every integer $d$ satisfies $d ∣ 0$ , so every integer is a common divisor of $0$ and $0$ .

1.2

$0 < 1$ : $1 = ι (1)$ lies in the image of $ι$ , hence $0 \leq 1$ ; and $1 \neq 0$ because $ι$ is injective and $1 \neq 0$ in $N$ .

2.1

For every $m \in Z$ , $m < m + 1$ : adding $m$ to $0 < 1$ gives $m \leq m + 1$ , and $m = m + 1$ would give $0 = 1$ after adding $- m$ , contrary to step 1.2.

step 1.2L1L2

3.1

$Z$ has no greatest element: if $m$ were one, then $m + 1 \in Z$ would give $m + 1 \leq m$ , while $m < m + 1$ by step 2.1, contradicting antisymmetry.

step 2.1L2

3.2

[L4] is not contradicted, since its hypothesis fails: $Z$ is not bounded above, because for any candidate bound $b$ the integer $b + 1$ exceeds it by step 2.1.

step 2.1L4

4.1

By steps 1.1 and 3.1 the set $D (0, 0)$ has no greatest element, so the refuted claim fails at $(0, 0)$ and no maximum defines $\gcd (0, 0)$ .

step 1.1step 3.1

5.1

What survives at $(0, 0)$ is the divisibility characterisation [L6]: $0 \geq 0$ , $0 ∣ 0$ , and every common divisor of $(0, 0)$ divides $0$ by [L3], so $0$ is the value that characterisation returns — which is exactly the convention adopted in Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ .

step 4.1L3L6∎

Remarks

The failure is only at $(0, 0)$ . For every other pair one of the two arguments is nonzero, and then the common divisors are bounded above by its absolute value (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 and the maximum exists.
The convention is not a patch over an inconvenience but over an absence. There is no integer that could serve as "the greatest common divisor of $0$ and $0$ " in the order of $Z$ , so a value has to be supplied; that it is $0$ is forced by the identities $\gcd$ is required to satisfy ( $\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$ ).

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

FALSE: For all integers $a$ and $b$ , $\gcd (a, b) \cdot lcm (a, b) = a b$

Statement

False claim: for all integers $a$ and $b$ ,

$\gcd (a, b) \cdot lcm (a, b) = a b$

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

The true statement 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 ∣$ , with an absolute value on the right: $\gcd (a, b) lcm (a, b) = ∣ a b ∣$ . The two differ as soon as $a b$ is negative, and $(a, b) = (- 2, 3)$ is a witness: there $\gcd (- 2, 3) = 1$ and $lcm (- 2, 3) = 6$ , so the left side is $6$ , while $a b = - 6$ .

Numerals. For $k \in N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers.

Facts & Assumptions

Given: The integers $- 2$ , $3$ and $6$ .

[L1]

$Z$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , $x \cdot (- 1) = - x$ , multiplication distributes over addition, and every $x$ has an additive inverse (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 (The integers form a totally ordered ring, Order on the integers).

[L3]

$\gcd (a, b) lcm (a, b) = ∣ a b ∣$ for all $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 ∣$ , Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ).

[L4]

[L5]

If $d ∣ u$ and $d ∣ v$ then $d ∣ u x + v y$ for all $x, y$ ; and $1 ∣ u$ for every $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$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L6]

$∣ x ∣ = x$ for $x \geq 0$ and $∣ x ∣ = - x$ for $x \leq 0$ ; $∣ 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$ ).

[L7]

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

[L8]

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

[L9]

The refuted claim: $\gcd (a, b) lcm (a, b) = a b$ for all integers $a, b$ .

Refutation

technique · direct

1.1

$\gcd (- 2, 3) = 1$ . Indeed $1 \geq 0$ , and $1 ∣ - 2$ and $1 ∣ 3$ by [L5]; and $(- 2) \cdot 1 + 3 \cdot 1 = 1$ , so every common divisor of $- 2$ and $3$ divides $1$ by [L5]. By [L4] this characterises $\gcd (- 2, 3)$ .

L1L4L5L8algebra

1.2

$(- 2) \cdot 3 = - 6$ , and $∣ - 6 ∣ = 6$ since $- 6 \leq 0$ and $- (- 6) = 6$ .

L1L2L6L8algebra

1.3

$6 \neq - 6$ : otherwise $6 + 6 = 0$ , that is $ι (12) = 0 = ι (0)$ , whence $12 = 0$ in $N$ , contradicting injectivity of $ι$ .

L1L8algebra

2.1

By [L3], $\gcd (- 2, 3) lcm (- 2, 3) = ∣ (- 2) \cdot 3 ∣ = 6$ ; with step 1.1 this reads $1 \cdot lcm (- 2, 3) = 6$ , so $lcm (- 2, 3) = 6$ by cancellation of the nonzero factor $1$ .

step 1.1step 1.2L1L3L7

3.1

Therefore $\gcd (- 2, 3) lcm (- 2, 3) = 1 \cdot 6 = 6$ , while $(- 2) \cdot 3 = - 6$ , and these differ: [L9] is false at $(a, b) = (- 2, 3)$ .

step 1.1step 1.2step 2.1step 1.3L1L9∎

Remarks

Every pair with $a b < 0$ refutes it, not just this one: $\gcd$ and $lcm$ are both nonnegative by construction (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$ ), so their product is nonnegative, while $a b$ is negative. The witness above is simply a small instance.
The claim is true when $a$ and $b$ are both nonnegative, which is why it is a natural slip: in that case $∣ a b ∣ = a b$ and the two statements coincide. Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ is the version that holds for all integers.
The absolute value is not the only convention doing work. At $a = 0$ the true identity reads $\gcd (0, b) \cdot 0 = 0 = ∣ 0 \cdot b ∣$ , which holds only because $lcm (0, b) = 0$ was fixed in Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ .

Divisibility and Greatest Common Divisors: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

gcd⁡(1071,462)=21gcd(1071,462)=21 by the Euclidean algorithm, with the back-substitution giving 21=7⋅462−3⋅107121=7⋅462−3⋅1071

Example

Facts & Assumptions

Verification

Remarks

Bézout coefficients are not unique: 1071⋅(−3)+462⋅7=211071⋅(−3)+462⋅7=21 and 1071⋅19+462⋅(−44)=211071⋅19+462⋅(−44)=21, and for nonzero a,ba,b every solution has the form (x0+tb/d, y0−ta/d)(x0​+tb/d,y0​−ta/d)

Example

Facts & Assumptions

Verification

Remarks

gcd⁡gcd at the boundary: gcd⁡(a,0)=∣a∣gcd(a,0)=∣a∣, gcd⁡(0,0)=0gcd(0,0)=0, and the convention gcd⁡(0,0)=0gcd(0,0)=0 is exactly what makes gcd⁡(ca,cb)=∣c∣gcd⁡(a,b)gcd(ca,cb)=∣c∣gcd(a,b) true at c=0c=0

Example

Facts & Assumptions

Verification

Remarks

ax+by=cax+by=c has an integer solution exactly when gcd⁡(a,b)∣cgcd(a,b)∣c: 6x+15y=96x+15y=9 is solvable and 6x+15y=76x+15y=7 is not

Example

Facts & Assumptions

Verification

Remarks

12Z+18Z=6Z12Z+18Z=6Z and 12Z∩18Z=36Z12Z∩18Z=36Z, the arithmetic of gcd⁡gcd and lcm⁡lcm read off the subgroups of (Z,+)(Z,+)

Example

Facts & Assumptions

Verification

Remarks

Consecutive Fibonacci numbers are coprime, and for every m∈Nm∈N the Euclidean algorithm on (Fm+3,Fm+2)(Fm+3​,Fm+2​) takes exactly m+1m+1 divisions, with quotient 11 in the first mm of them and quotient 22 in the last

Example

Facts & Assumptions

Verification

Remarks

6∣4⋅96∣4⋅9 while 6∤46∤4 and 6∤96∤9: dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails

Statement refuted

Facts & Assumptions

Counterexample

Remarks

The common divisors of (0,0)(0,0) are all of ZZ and have no greatest element in the order of ZZ, so gcd⁡(0,0)gcd(0,0) cannot be defined as a maximum and is fixed by convention

Statement refuted

Facts & Assumptions

Counterexample

Remarks

FALSE: For all integers aa and bb, gcd⁡(a,b)⋅lcm⁡(a,b)=abgcd(a,b)⋅lcm(a,b)=ab

Statement

Facts & Assumptions

Refutation

Remarks

Sources

$\gcd (1071, 462) = 21$ by the Euclidean algorithm, with the back-substitution giving $21 = 7 \cdot 462 - 3 \cdot 1071$

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

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

$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

$12 Z + 18 Z = 6 Z$ and $12 Z \cap 18 Z = 36 Z$ , the arithmetic of $\gcd$ and $lcm$ read off the subgroups of $(Z, +)$

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

$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

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

FALSE: For all integers $a$ and $b$ , $\gcd (a, b) \cdot lcm (a, b) = a b$