How this instrument works
The greatest common divisor (GCD) of two whole numbers is the largest whole number that divides evenly into both, with no remainder left over. Every pair of positive whole numbers shares at least the trivial common divisor 1, but most pairs share something larger, and finding the biggest one is exactly what this calculator does, using the same efficient method mathematicians have relied on for over two thousand years: the Euclidean algorithm, which repeatedly replaces the larger number with the remainder of dividing it by the smaller, until nothing remains but the answer.
The GCD is exactly the number needed to reduce any fraction to its lowest terms: dividing both a fraction's numerator and denominator by their GCD always produces the smallest possible equivalent fraction, with nothing further to simplify. This is the single most common practical use of the GCD outside pure number theory.
Two numbers whose GCD is exactly 1 are called coprime (or relatively prime) — they share no common factor larger than 1, even if neither number is itself prime. Coprimality shows up constantly in cryptography, modular arithmetic, and any situation where two quantities need to be guaranteed to have no hidden shared structure.
- Enter the first whole number into the First number field.
- Enter the second whole number into the Second number field.
- Read Greatest common divisor: the largest number that divides both evenly.
Worked example — the GCD of 48 and 18
The greatest common divisor of 48 and 18 is 6 — check that 48 ⁄ 6 = 8 and 18 ⁄ 6 = 3, both exact, and no larger number divides both cleanly. This is exactly the number needed to reduce the fraction 48⁄18 down to its simplest form, 8⁄3.
Compare 17 and 5, two numbers with no factors in common beyond the trivial one: their GCD is exactly 1, making them coprime, and the fraction 17⁄5 is already in its lowest possible terms with nothing left to simplify.
Questions
What is the greatest common divisor?
The GCD of two whole numbers is the largest whole number that divides evenly into both, with no remainder. Every pair of positive integers has a GCD, since 1 always divides evenly into anything, setting the smallest possible floor.
How is the GCD calculated?
The Euclidean algorithm finds it efficiently: repeatedly replace the larger number with the remainder of dividing it by the smaller, and continue until the remainder reaches zero — whatever number remains at that point is the GCD, found without ever listing out every factor of either number.
What does it mean for two numbers to be coprime?
Two numbers are coprime (or relatively prime) when their GCD is exactly 1 — they share no common factor larger than 1, even if one or both numbers are themselves composite. 8 and 15, for instance, are coprime despite neither being prime.
How does the GCD help simplify fractions?
Dividing both a fraction's numerator and denominator by their GCD always produces the smallest equivalent fraction, with nothing further to reduce. This is the standard method for putting any fraction into lowest terms.
What is the relationship between GCD and LCM?
For any two positive whole numbers, their GCD multiplied by their LCM (least common multiple) always equals the product of the two numbers themselves: gcd(a,b) × lcm(a,b) = a × b, a useful identity for finding one once the other is known.