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

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.

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.

Depends on

Used by

Dependency tree · two levels

23 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Euclidean algorithm (Wikipedia) (standard reference, not scraped)

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)