TFT

GCD / HCF Calculator – Find Greatest Common Divisor Online

Calculate the GCD or HCF of two or more numbers instantly with our free online calculator. Uses the Euclidean algorithm to find the greatest common divisor with step-by-step solutions.

Examples:

Understanding GCD/HCF

The Greatest Common Divisor (GCD), also called the Highest Common Factor (HCF), is the largest number that divides two or more numbers without leaving a remainder. It's a fundamental concept in number theory with practical applications in simplifying fractions and solving problems involving ratios.

For example, the GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly. The factors of 12 are 1, 2, 3, 4, 6, 12. The factors of 18 are 1, 2, 3, 6, 9, 18. The common factors are 1, 2, 3, 6, and the greatest is 6.

The Euclidean Algorithm

The Euclidean algorithm is an efficient method for finding the GCD. It's based on a simple principle:

GCD(a, b) = GCD(b, a mod b)
  1. 1

    Divide the larger number by the smaller

    Find the quotient and remainder.

  2. 2

    Replace and repeat

    Replace the larger number with the smaller, and the smaller with the remainder.

  3. 3

    Continue until remainder is zero

    When the remainder becomes zero, the last non-zero remainder is the GCD.

Worked Examples

Example 1: GCD of 48 and 60

60 = 48 × 1 + 12
48 = 12 × 4 + 0
Remainder is 0, so GCD = 12
Verification: 48÷12=4 ✓, 60÷12=5 ✓

Example 2: GCD of 100 and 35

100 = 35 × 2 + 30
35 = 30 × 1 + 5
30 = 5 × 6 + 0
GCD = 5
Verification: 100÷5=20 ✓, 35÷5=7 ✓

Example 3: GCD of 17 and 23 (coprime)

23 = 17 × 1 + 6
17 = 6 × 2 + 5
6 = 5 × 1 + 1
5 = 1 × 5 + 0
GCD = 1
When GCD = 1, numbers are coprime (relatively prime)

Example 4: GCD of Three Numbers (12, 18, 24)

First find GCD(12, 18):
18 = 12 × 1 + 6
12 = 6 × 2 + 0
GCD(12, 18) = 6
Now find GCD(6, 24):
24 = 6 × 4 + 0
GCD = 6
GCD(12, 18, 24) = 6

Quick Fact

The Euclidean algorithm is over 2,300 years old, appearing in Euclid's Elements around 300 BCE. It's one of the oldest algorithms still in common use today. Donald Knuth called it "the granddaddy of all algorithms."

Frequently Asked Questions

What's the difference between GCD and HCF?

There's no difference – they're the same thing. GCD (Greatest Common Divisor) is more common in American mathematics. HCF (Highest Common Factor) is often used in British and Indian mathematics. Both refer to the largest number that divides all given numbers.

Why use the Euclidean algorithm instead of listing factors?

For small numbers, listing factors works fine. But for large numbers, the Euclidean algorithm is much faster. It reduces the problem size with each step, guaranteeing a quick solution even for very large numbers.

What are coprime numbers?

Two numbers are coprime (or relatively prime) if their GCD is 1. They share no common factors other than 1. Examples: 8 and 15, 14 and 25, any two different prime numbers.

How is GCD used to simplify fractions?

Divide both numerator and denominator by their GCD. For 48/60, GCD(48,60) = 12, so 48÷12 = 4 and 60÷12 = 5, giving 4/5. This gives the fraction in lowest terms.

Can GCD be found for more than two numbers?

Yes. Find the GCD of the first two numbers, then find the GCD of that result with the third number, and so on. GCD(a, b, c) = GCD(GCD(a, b), c).

What's the relationship between GCD and LCM?

For any two numbers a and b: GCD(a,b) × LCM(a,b) = a × b. So if you know the GCD, you can find the LCM: LCM = (a × b) / GCD.

Other Free Tools

LCM Calculator – Find Least Common Multiple Online

Calculate the Least Common Multiple (LCM) of two or more numbers instantly with our free online LCM calculator. Get accurate results with step-by-step explanations.

Factor Calculator – Find All Factors of Any Integer

Find all factors of any integer instantly with our free online factor calculator. Lists every factor in ascending order – perfect for simplifying fractions and solving number theory problems.

Prime Factorization Calculator – Find Prime Factors Instantly

Find the prime factorization of any number with our free online calculator. Displays all prime factors in exponential form and as a factor tree for easy understanding.

Divisibility Checker – Test Divisibility Rules Instantly

Check if any number is divisible by another with our free online divisibility checker. Displays the relevant divisibility rule and provides instant yes or no results.

Factors List Generator – Find All Factors of a Number

Generate a complete sorted list of all factors of any number instantly with our free online factors calculator. Ideal for math homework, LCM/GCD problems, and number theory.

Fraction Calculator – Add, Subtract, Multiply & Divide Fractions

Easily add, subtract, multiply, and divide fractions with our free online fraction calculator. Get instant simplified results and step-by-step solutions for all fraction operations.

Decimal to Fraction Converter – Convert Decimals to Fractions

Convert any decimal to a fraction instantly with our free online decimal to fraction converter. Returns fully simplified fractions with clear step-by-step conversion process.

Modular Arithmetic Calculator – Compute mod n Operations

Perform modular arithmetic operations including addition, subtraction, multiplication, and exponentiation under any modulus with our free online calculator.