GCD Calculator - Greatest Common Divisor

This greatest common divisor (GCD or GCF) calculator can be used to find the GCD or GCF of two or more positive integers as long as the integers are smaller than 1 trillion. To use the calculator, provide some values, then click the "Calculate" button. To find the GCD of more than two numbers, select the "Find GCD of more than two numbers" checkbox and provide numbers separated by a comma or semicolon.

What is the GCD or GCF?

The greatest common divisor (GCD), also referred to as the greatest common factor (GCF), of two or more non-zero integers is the largest integer that divides them. For example, the greatest common divisor of 36 and 54, denoted GCD(36, 54), is 18. The GCD is commonly used for finding a common denominator to simplify fractions.

How to find the GCD or GCF?

There are various ways to find the GCD that vary in complexity and efficiency.

Factoring

Listing all the factors of each integer is one way to find their greatest common divisor. For example, to find GCD(36, 54), list the factors of 36 and 54 then identify the largest shared factor:

Thus, GCD(36,54) = 18. Although this method is an effective way to find the GCD, as the numbers get larger, using this method gets more tedious and inefficient, so it should only be used when the numbers are relatively small.

Prime factorization

Prime factorization involves decomposing a number into a product of its prime factors. All numbers have a unique prime factorization, so finding all the shared prime factors between two numbers, then computing their product, yields the GCD of the two numbers. For example, the prime factorizations of 36 and 54 are shown below:

36 and 54 share the prime factors 2, 3, and 3, so the product of their shared prime factors, or their GCD, is

2 × 3 × 3 = 18,

which matches the solution obtained using the factoring method. Like the factoring method, the prime factorization method is effective when the numbers are relatively small, but gets more tedious as numbers get larger.

Euclidean algorithm

The Euclidean algorithm is one of the most efficient ways to find the GCD between a set of numbers. It requires some understanding of the modulo operator. The modulo operator indicates the process of division with a remainder, where this remainder is referred to as the modulus; this terminology is important for understanding the algorithm described below. Given two numbers, such as 12 and 8, the modulus is:

12 mod 8 = 4

This is because 8 can be divided into 12 for 1 time with a remainder of 4. The modulo operator may also be indicated using a % symbol: 12 % 8. Note that the % in this case is just a symbol that was selected and is used by convention to indicate the modulo operator, and has nothing to do with percentages.

The Euclidean algorithm makes use of the following three properties:

1. GCD(a,0) = a
2. GCD(0,b) = b
3. GCD(a,b) = GCD(b,a mod b)

The third property is the most important of the three because it efficiently reduces the GCD to a simpler problem each time it is applied. Thus, to use the Euclidean algorithm to compute GCD(a, b), where a and b represent two integers, R is the remainder, and a > b, use the following steps:

1. Reduce GCD(a, b) to GCD(b, a mod b) by finding a mod b.
2. Treat GCD(b, a mod b) as the new GCD(a, b).
3. Repeat steps 1 and 2 until b = 0
4. Then, GCD(a, 0) = a

For example, to find GCD(54, 36) using the Euclidean algorithm:

Thus, using property 1 from above, since the GCD is in the form GCD(a, 0), the GCD = a, or 18.

GCD of more than two numbers

The GCD of more than two numbers can be found using the same methods. For factoring and prime factorization, the addition of more numbers doesn't change how the GCD is computed. However, as these methods can already be quite tedious, adding more numbers only adds to this tedium, and the Euclidean algorithm is still the most efficient method for calculating the GCD of more than two numbers.

To use the Euclidean algorithm to compute the GCD of more than two numbers, first calculate the GCD between two of the numbers, then calculate the GCD of the result and the third number. Given 3 numbers, a, b, and c:

GCD(a,b,c) = GCD[GCD(a,b),c] = GCD[GCD(a,c),b] = GCD[GCD(b,c),a]

The above property of GCDs can be expanded for any number of terms. Essentially, the order in which we compute the GCD doesn't matter, so the GCD of a set of numbers can be calculated by determining the GCD of two of the numbers at a time, then computing the GCD of the result and another of the terms. For example:

Thus GCD(64, 42) = 2; plugging this into the original expression,

Thus, GCD(12, 42, 64) = 2.