# Euclidean algorithm

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

The Euclidean algorithm computes the gcd using exact quotient-remainder divisions, gcd invariance and strictly decreasing nonnegative remainders.

mko-euclidean-algorithm · algorithm · v0.10.0



## 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

[Euclid and back-substitution for signed inputs](https://ocme.evemisslab.com/en/derivations/derivation-mko-euclidean-algorithm-01/)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](https://ocme.evemisslab.com/en/mko/mko-gcd-coprime/) — The gcd is the target invariant.
- [Natural-number divisibility](https://ocme.evemisslab.com/en/mko/mko-natural-divisibility/) — Division with remainder supplies each step.
- [Algorithm correctness](https://ocme.evemisslab.com/en/mko/mko-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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/euclidean-algorithm.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-euclidean-algorithm/index.md)