GCD Calculator
Find the greatest common divisor of two or more whole numbers.
What the GCD Calculator does
The greatest common divisor is the largest number that divides every value evenly. The Euclidean algorithm finds it fast by repeatedly replacing the larger number with the remainder of the division.
Formula
gcd(a, b) = gcd(b, a mod b), stopping when b = 0gcd(a,b) × lcm(a,b) = a × b
Inputs explained
| Input | Unit | Required | Notes |
|---|---|---|---|
| Numbers | text | Yes | Separate values with commas, spaces or new lines. |
How to use it
- Enter Numbers.
- Select Calculate.
Worked example
Simplify the fraction 48/180.
- Numbers
- 48, 180
gcd = 12, so 48/180 reduces to 4/15.
Reading the result
- The GCD is what you divide by to reduce a fraction to lowest terms: 18/24 shares a GCD of 6, giving 3/4.
- Two numbers whose GCD is 1 are coprime, which is the condition modular inverses and much of cryptography depend on.
Common mistakes
- Confusing the GCD with the LCM. The GCD is never larger than the smallest input; the LCM is never smaller than the largest.
- Assuming GCD(0, n) is undefined. It is n, because every number divides zero exactly.
Frequently asked questions
Is GCD the same as HCF?
Yes. Greatest common divisor, greatest common factor and highest common factor all mean the same thing.