Greatest common divisor and coprimality

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

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