The gcd is reachable
Surprising fact: the greatest common divisor isn't just an abstract measurement — it is CONSTRUCTIBLE from the two numbers using only multiplication and addition. Among all positive numbers of the form ax + by, the smallest one is exactly the gcd. Well-ordering guarantees a smallest exists; a little algebra shows it divides both a and b.
With an unlimited supply of 12-step forward moves and 18-step backward moves you can land exactly 6 steps from where you started — and 6 = gcd(12,18) is the closest you can ever get.
gcd(12, 18) = 6, and indeed 12×(−1) + 18×(1) = 6. For gcd(7, 5) = 1: 7×3 + 5×(−4) = 21 − 20 = 1.
Bezout's identity is the key that unlocks Euclid's lemma and hence unique factorization — and computing those x, y (extended Euclidean algorithm) is how RSA decryption keys are generated.
Level 1 The precise statement
For integers a, b not both zero there exist integers x, y with gcd(a, b) = a*x + b*y.
Level 2 The proof
Level 3 What it stands on (3 direct)
- Well-Ordering Principle (axiom)
- Integers form a commutative ring (axiom)
- Divisibility (definition)
- Greatest common divisor (definition)
- Bezout's identity (lemma)
Level 4 The verified record
This page is generated from a machine-checked node. The kernel confirms its dependencies resolve, nothing is circular, and it grounds in axioms (foundation: peano). The content hash below makes tampering evident.
2 downstream results would collapse with it. See the blast radius on the graph →