The biggest shared factor
gcd(12, 18) = 6: it is the biggest 'common ingredient' of the two numbers. It measures exactly how much two numbers overlap multiplicatively — gcd 1 means they share nothing at all (coprime).
Two ribbons, 12 m and 18 m, to be cut into equal pieces with nothing wasted: the longest possible piece is 6 m — the gcd.
gcd(24, 36): divisors of 24 are 1,2,3,4,6,8,12,24; of 36 are 1,2,3,4,6,9,12,18,36. Largest common: 12.
Reducing fractions to lowest terms IS dividing by the gcd. Euclid's gcd algorithm — arguably the oldest algorithm still in daily use — runs inside every cryptographic key exchange.
Level 1 The precise statement
gcd(a, b) is the largest integer d such that d | a and d | b.
Level 3 What it stands on (1 direct)
- Integers form a commutative ring (axiom)
- Divisibility (definition)
- Greatest common divisor (definition)
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.
3 downstream results would collapse with it. See the blast radius on the graph →