Sign up
GCD / HCF calculator →

GCD / HCF guide

The Greatest Common Divisor (GCD) Calculator finds the largest positive integer that divides two or more numbers without a remainder. It shows the step-by-step Euclidean algorithm and lists all common divisors.

Worked examples

Find the GCD of two numbers

  1. Enter 12, 18 in the input field.
  2. Click Calculate.
Result: GCD = 6

The divisors of 12 are 1, 2, 3, 4, 6, 12. The divisors of 18 are 1, 2, 3, 6, 9, 18. The largest shared divisor is 6.

Find the GCD of three numbers

  1. Enter 24, 36, 60.
  2. Click Calculate.
Result: GCD = 12

The Euclidean algorithm is applied iteratively: GCD(24, 36) = 12, then GCD(12, 60) = 12.

Check if two numbers are coprime

  1. Enter 7, 13.
  2. Click Calculate.
Result: GCD = 1

The only common divisor is 1, which means 7 and 13 are coprime (relatively prime).

Tips

  • •The GCD is also known as the Highest Common Factor (HCF).
  • •Use the "View GCD Reference Tool" to experiment with two specific numbers.
  • •The Euclidean algorithm is one of the oldest algorithms still in use today.

Frequently asked questions

What is the Greatest Common Divisor (GCD)?
The largest positive integer that divides two or more numbers without leaving a remainder.
What is another name for GCD?
It is also known as the Highest Common Factor (HCF) or Greatest Common Factor (GCF).
What is the Euclidean algorithm?
An ancient, efficient method to find the GCD. It repeatedly replaces the larger number with the remainder of dividing the larger by the smaller until the remainder is zero.
What does it mean if the GCD is 1?
It means the two numbers are coprime (relatively prime). They share no common factors other than 1.
Can the GCD be negative?
No. The GCD is always defined as a positive integer. The calculator takes the absolute value of any inputs.
What is the GCD of 0 and a number?
GCD(0, n) = |n|, because every non-zero number divides zero evenly.
How is GCD used in simplifying fractions?
To simplify a fraction a/b to its lowest terms, divide both the numerator and denominator by their GCD.
How does GCD relate to LCM?
For any two positive integers a and b: GCD(a,b) × LCM(a,b) = a × b.
What is the GCD of two prime numbers?
It is always 1, because prime numbers have no other divisors besides 1 and themselves.
How does the Euclidean algorithm work?
It uses the property that GCD(a, b) = GCD(b, a mod b). By repeatedly taking remainders, the numbers shrink rapidly until the remainder is 0.
Can I find the GCD of more than two numbers?
Yes. The calculator iteratively applies the GCD function to each number in the list.
Does the calculator show all common divisors?
Yes. It lists every number that divides evenly into all inputs.
What are some real-world applications of GCD?
Simplifying gear ratios, arranging objects into equal-sized groups, and cryptography (like RSA).
Can GCD handle decimals?
No. GCD is only defined for integers. The calculator will return an error if you input decimals.
What is the GCD of 100 and 10?
10. If one number is a multiple of the other, the smaller number is the GCD.
How fast is the Euclidean algorithm?
It is highly efficient, running in logarithmic time relative to the size of the numbers.
Are there other algorithms to find GCD?
Yes, such as prime factorization or the binary GCD algorithm, but the Euclidean algorithm is the most common.
Does this tool use absolute values?
Yes, GCD is always a positive integer, regardless of whether the inputs are negative.
Open the calculator All guides