Euclidean algorithm

Mathematical statement

At every nonzero-divisor step check a=bq+r and 0≤r<|b|, with quotient q and remainder r. Separate gcd invariance, descent/termination and the final nonnegative gcd. The extended version back-substitutes and rechecks ax+by=gcd; zero inputs use gcd(0,0)=0 without division by zero.

Representative formula (exact TeX)

a=b(q)+r

Assumptions

• Inputs are integers in the safe range, and the main chain runs on their absolute values.
• Restore original input signs in Bezout coefficients and check the exact identity.

Symbol scope

• q — Euclidean quotient
• r — Euclidean remainder

Intuition, definition, and misconceptions

Every division preserves the gcd and strictly lowers the nonnegative remainder until zero.

The last nonzero value gives the nonnegative gcd, with zero-input conventions stated separately.

Bezout coefficients require extended back-substitution and an identity check, not a guess from the gcd alone.

Producing a number alone does not establish correctness, and division must not continue with a zero divisor.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Greatest common divisor and coprimality — The gcd is the target invariant.
• Natural-number divisibility — Division with remainder supplies each step.
• Algorithm correctness — Invariance and termination are separate obligations.

Verification boundary

Only the exact integer algorithm is handled; bit-complexity optimality is not claimed.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add binary gcd and modular-inverse construction.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.