TheoremStatement: 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.

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.1L1L2L3construct

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

1.2basegivenL1

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

1.3ih

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

2.1step 1.3L1L2L8

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.

3.1step 1.2step 2.1L4

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.

4.1step 3.1L5L6choose

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

5.1step 3.1step 4.1L1L6L7

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

6.1step 5.1givenL5L7

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

7.1step 3.1step 6.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$ .

8.1step 6.1step 7.1L2

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

9.1step 3.1step 7.1step 8.1L9discharge-induction∎

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.

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.

Depends on

Dependency tree · 2 levels

Sources

Euclidean algorithm (Wikipedia)

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)