Greatest Common Factor Calculator

The greatest common divisor (GCD) of two numbers is the largest number that will divide evenly into both of the given numbers. For example, the GCD of 12 and 24 is 12, since 12 divides evenly into both numbers and is the largest number to do so. The GCD of 60 and 61 is 1, since this is the only factor they share. When the GCD of two numbers equals 1, the numbers are said to be relatively prime to one another. You can use the calculator on the left or follow the explanation below.

How to Compute the GCD by Hand

Example 1: Find the greatest common factor of 180 and 144. The easiest way to do this is to find the prime factorization of both numbers using a factor tree, then calculate the product of all the common prime factors, accounting for repeated prime factors.

The prime factorizations of 144 and 180 are

144 = 2*2*2*2*3*3

180 = 2*2*3*3*5

The intersection of the sets {2, 2, 2, 2, 3, 3} and {2, 2, 3, 3, 5} is {2, 2, 3, 3}. Notice that 3 is in this list twice since both numbers are divisible by 3*3. The factor 2 is also in this list twice since both numbers are divisible by 2*2, but 180 is not divisible by any more factors of 2. The factor 5 does not appear in the set at all since it is not common to 144 and 180.

Thus, the greatest common divisor of 144 and 180 is 2*2*3*3 = 36.


Example 2: Of the three numbers 196, 1096, and 9610, which pair has the greatest GCD? For this problem we need to compute GCD(196, 1096), GCD(196, 9610), and GCD(1096, 9610). To start, let's find the prime factorization of each number:

196 = 2*2*7*7

1096 = 2*2*2*137

9610 = 2*5*31*31

Thus,

GCD(196, 1096) = 2*2 = 4

GCD(196, 9610) = 2

GCD(1096, 9610) = 2

So the pair of 196 and 1096 has the greatest GCD.

Relation Between GCD and LCM

The product of the LCM and GCD of two numbers is equal to the product of the two numbers. That is,

LCM(a,b)*GCD(a,b) = ab

The main consequence of this expression is that you can always find the GCD if you know the LCM and vice versa:

LCM(a,b) = ab/GCD(a,b)

GCD(a,b) = ab/LCM(a,b)

For example, since the LCM of 144 and 180 is 720, you can compute the GCD of the two numbers more quickly:

GCD(144, 180) = 144*180/720 = 36

© Had2Know 2010