Greatest Common Divisor Calculator
Use this tool to find the GCD (Greatest Common Divisor) of two or more integers. Enter two required integers and optionally include additional numbers.
Tip: You can use negative values. The calculator uses absolute values when computing the GCD.
What is a GCD?
The greatest common divisor of a set of integers is the largest positive integer that divides each number exactly (without remainder). It is often written as GCD(a, b), and in some books you may see it called the greatest common factor (GCF) or highest common factor (HCF).
For example, the divisors of 18 are 1, 2, 3, 6, 9, and 18. The divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24. Their common divisors are 1, 2, 3, and 6, so the greatest common divisor is 6.
Why this calculator is useful
A good GCD calculator saves time and avoids arithmetic mistakes, especially when working with large numbers. It is useful in:
- Reducing fractions to simplest form
- Number theory exercises and proofs
- Computer science algorithms and cryptography basics
- Engineering and measurement where quantities need common units
How the Euclidean Algorithm works
The fastest standard method for finding the GCD is the Euclidean algorithm. Instead of listing all divisors, it repeatedly replaces the pair of numbers with a smaller pair:
If you have numbers a and b, compute a mod b (the remainder when a is divided by b), then repeat with
(b, a mod b). Continue until the remainder is zero. The last non-zero value is the GCD.
Example: GCD(84, 30)
- 84 = 30 × 2 + 24
- 30 = 24 × 1 + 6
- 24 = 6 × 4 + 0
The last non-zero remainder is 6, so GCD(84, 30) = 6.
Using GCD to simplify fractions
Suppose you want to simplify the fraction 84/30. First compute GCD(84, 30) = 6. Then divide numerator and denominator by 6:
84/30 = 14/5
This is why GCD appears everywhere in algebra and arithmetic classes: it gives the cleanest reduced form.
GCD and LCM relationship
For two integers a and b, there is an important relationship:
GCD(a, b) × LCM(a, b) = |a × b|
Once you know the GCD, you can get the least common multiple (LCM) quickly:
LCM(a, b) = |a × b| / GCD(a, b), as long as both numbers are not zero.
Common edge cases
1) One number is zero
GCD(a, 0) = |a| for any non-zero integer a. For example, GCD(45, 0) = 45.
2) Both numbers are zero
GCD(0, 0) is undefined in standard arithmetic. This calculator reports that case clearly.
3) Negative numbers
The sign does not change the GCD because divisibility is based on absolute value. So GCD(-24, 18) = 6.
Quick practice problems
- GCD(56, 98) = 14
- GCD(101, 103) = 1 (coprime numbers)
- GCD(120, 210, 330) = 30
Final thoughts
The GCD is a foundational concept that connects school arithmetic, higher mathematics, and real-world problem solving. Whether you are simplifying fractions, checking if numbers are coprime, or learning algorithmic thinking, understanding the GCD gives you a strong base.
Use the calculator above whenever you need a quick answer, and enable the step-by-step option to build intuition for the Euclidean algorithm.