GCD / HCF Calculator

Find the Greatest Common Divisor (Highest Common Factor)

First Number

Second Number

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

What is the difference between GCD and HCF?

There is no difference. GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are two names for the same concept. Different regions and textbooks prefer different terms, but they mean exactly the same thing.

How do I find GCD of more than two numbers?

Find GCD of the first two numbers, then find GCD of that result with the third number, and continue. For GCD(12, 18, 24): first GCD(12, 18) = 6, then GCD(6, 24) = 6. So GCD(12, 18, 24) = 6.

What does it mean if GCD is 1?

When GCD equals 1, the numbers are coprime (or relatively prime). They share no common factors other than 1. For example, 8 and 15 are coprime because their only common factor is 1, even though neither number is prime.

Can GCD be used for decimal numbers?

GCD is defined for integers only. For decimals, multiply all numbers by a power of 10 to make them integers, find the GCD, then divide by the same power of 10. However, this is rarely needed in practice.

What are practical uses of GCD?

GCD is used to simplify fractions, find common denominators, solve Diophantine equations, and in cryptography (RSA encryption relies on properties related to GCD). It is also useful for dividing things into equal groups - like finding the largest tile size that fits evenly into two different room dimensions.

Other Free Tools

Search tools