Greatest Common Divisor (GCD) Calculator

1. What is Greatest Common Divisor (GCD)?
2. How to calculate Greatest Common Divisor
3. Practical Examples

    What is Greatest Common Divisor (GCD)?

The greatest common divisor (gcd), also known as greatest common factor (gcf), highest common factor (hcf), highest common divisor (hcd) and greatest common measure (gcm), is applicable to sets of 2 or more integers different from zero and is the largest positive integers that divides each of them without remainder. The GCD of 1 and any number is 1. It is easy to find the gcd for small numbers like 10 and 15 (5), but it becomes progressively harder for larger numbers so a GCD calculator is of great utility in such scenarios.

To illustrate the concept, let us say we want to find gcd(60,24) (greatest common divisor of 60 and 24). We can list all divisors of 60 and 24:

Divisors of 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30

Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24

One can observe that the common numbers in the sequences are 1, 2, 3, 4, 6, and 12, of which 12 is the largest, so gcd(60,24) is 12, which can be easily confirmed using this greatest common divisor calculator.

Greatest common divisors are useful for reducing fractions to their lowest terms. To use the above example, let's take the fraction 24/60. Since gcd(60,24) = 12, we divide the numerator and denominator by 12 and arrive at 2/5, which is not reducible any further as both 2 and 5 are prime numbers. The are also coprime numbers in this case: a coprime set of numbers is such a set in which their greatest common divisor is 1.

    How to calculate Greatest Common Divisor

There are different methods: prime factorization, Euclid's algorithm, binary method, a method using the least common multiple, Thomae's function, and others. The computation complexity is high in all cases for large numbers. For example, prime factorization is only feasible for small integers.

Using our greatest common divisor calculator is free and very easy to do online, both on a desktop and mobile device, so it is a great way to save time and effort.

    Practical Examples

Euclid's algorithm is gcd(a, b) = gcd(a - b, b) if a > b and gcd(a, b) = gcd(a, b - a) if b > a. It uses the observation that the greatest common divisor calculated for two numbers also divides their difference.

For example, to compute gcd(60,24), divide 60 by 24 to get a quotient of 2 and a remainder of 12. Then divide 24 by 12 to get a quotent of 2 and a remainder of 0, meaning that the greatest common divisor is 12.

The LCM method is something you can try using our LCM calculator since gcd(a, b) = a x b / lcm(a, b).