# Greatest common divisor and coprimality

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

The natural number gcd(a,b) divides both a and b and is divisible by every common divisor; the inputs are coprime when their gcd is 1.

mko-gcd-coprime · definition · v0.10.0



## Mathematical statement

The natural number d=gcd(a,b) is characterized by d∣a and d∣b, with c∣d for every natural c that divides both a and b. Adopt gcd(0,0)=0. The inputs a and b are coprime exactly when gcd(a,b)=1.





## Representative formula (exact TeX)

d=g(a,b)





## Assumptions


- The inputs a and b are natural numbers, with either or both allowed to be 0.
- Greatestness is characterized by divisibility, using the usual natural-number gcd convention and the explicitly stated zero case.





## Symbol scope


- d — greatest common divisor
- g — greatest-common-divisor operation
- a — first natural-number input
- b — second natural-number input





## Intuition, definition, and misconceptions

The Euclidean algorithm repeatedly uses remainders with nonzero divisors until the remainder is zero. The final nonzero value is the gcd; use the separate convention 0 for (0,0).

A candidate d must divide both inputs and be divisible by every common divisor. Finding one large common divisor alone is insufficient.

Coprimality does not mean that both numbers are prime. For example, 8 and 15 are coprime; 0 and 1 are coprime, whereas 0 and an integer greater than 1 are not.

Do not call an arbitrary common divisor the gcd or interpret coprimality as requiring two prime inputs.





## Adopted derivation guide

[Greatest common divisor and coprimality: checking Euclid's algorithm against the divisibility characterization](https://ocme.evemisslab.com/en/derivations/derivation-mko-gcd-coprime-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Natural-number divisibility](https://ocme.evemisslab.com/en/mko/mko-natural-divisibility/) — Common divisors and greatestness are expressed through divisibility.





## Verification boundary

The natural-number Euclidean algorithm can be recomputed exactly; this slice constructs no formal proof of an integer-coefficient Bézout identity.

not_formalized

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





## Next obligation

Bind Nat.gcd, Nat.dvd_gcd, Nat.gcd_dvd_left/right, gcd_greatest and Nat.Coprime.





## 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/gcd-coprime.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-gcd-coprime/index.md)