GCD / HCF Calculator
Find the Greatest Common Divisor (Highest Common Factor)
How to Use This GCD Calculator
Enter the first number
Input any positive integer. For example, enter 48 to find the GCD of 48 and another number.
Enter the second number
Input the second positive integer. The calculator will find the largest number that divides both evenly.
Click Calculate
The calculator uses the Euclidean algorithm to find the GCD instantly. The result is the largest number that divides both inputs without a remainder.
GCD Examples Reference Table
| Number 1 | Number 2 | GCD | Common Factors |
|---|---|---|---|
| 12 | 18 | 6 | 1, 2, 3, 6 |
| 24 | 36 | 12 | 1, 2, 3, 4, 6, 12 |
| 48 | 18 | 6 | 1, 2, 3, 6 |
| 17 | 23 | 1 | 1 (coprime) |
| 100 | 75 | 25 | 1, 5, 25 |
| 144 | 60 | 12 | 1, 2, 3, 4, 6, 12 |
Note: When GCD equals 1, the numbers are called coprime or relatively prime - they share no common factors other than 1.
Understanding Greatest Common Divisor
What is GCD?
The Greatest Common Divisor (GCD), also called Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder. For example, the GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.
The Euclidean Algorithm
This calculator uses the Euclidean algorithm, one of the oldest known algorithms (dating back to 300 BCE). To find GCD(a, b): divide a by b, get the remainder r, then replace a with b and b with r. Repeat until the remainder is 0. The last non-zero remainder is the GCD. For GCD(48, 18): 48÷18=2 remainder 12, then 18÷12=1 remainder 6, then 12÷6=2 remainder 0. GCD is 6.
GCD and Fraction Simplification
GCD is essential for simplifying fractions. To reduce 48/18 to lowest terms, divide both numerator and denominator by their GCD (which is 6): 48÷6=7, 18÷6=3, so 48/18 = 8/3. This gives the fraction in its simplest form.
Tips for Finding GCD
Use prime factorization for small numbers
Break each number into prime factors, then multiply the common factors. For 24 (2³×3) and 36 (2²×3²), common factors are 2²×3 = 12.
Recognize coprime numbers quickly
If both numbers are prime and different, their GCD is always 1. Also, consecutive integers (like 15 and 16) are always coprime with GCD = 1.
Use the relationship with LCM
GCD(a,b) × LCM(a,b) = a × b. If you know the LCM, you can find GCD by dividing the product by the LCM. This is useful for checking your work.
GCD works for negative numbers too
GCD is always positive. GCD(-48, 18) = GCD(48, 18) = 6. The calculator handles negative inputs by using absolute values.
Frequently Asked Questions
Other Free Tools
Lcm Calculator
LCM Calculator – Find Least Common Multiple Online
Prime Factorization Calculator
Prime Factorization Calculator – Find Prime Factors
Prime Checker
Prime Number Checker – Is This Number Prime?
Factorial Calculator
Factorial Calculator
Combination Calculator
Combination Calculator
Permutation Calculator
Permutation Calculator