Greatest Common Divisors

What is the greatest common divisor?  By definition, the greatest common divisor is the largest integer that divides without remainder into a set of integers (at least one of which is not zero). An integer is a positive or negative whole number or zero.  Sometimes a divisor is also called a factor so you may hear greatest common factor in place of greatest common divisor.  We write this as GDF or GCD.  Watch this youtube video from Khan Academy to see how to find the greatest common divisor.

Example 1 - Intersection of Sets

The video above is a great example of how to find the GCD using the intersection of sets.  Lets use this information and do an example on our own. Find the GCD of the integers 54 and 81.

First we need to find the divisors, or factors, of 54.

D54 = {1, 2, 3, 6, 9, 18, 27, 54}

and the divisors of 81.

D81= {1, 3, 9, 27, 81}

Next we need to look at the common divisors between 54 and 81.

D54 and D81 = {1, 3, 9, 27}

Looking at the list of common divisors we can see that 27 is the greatest number.  Therefore, the

GCD (54, 81) = 27

Example 2 - Prime Factorization

Another way to find the greatest common divisor is by prime factorization.  Prime Factorization is finding which prime numbers multiply together to make the original number.  Using the same integers above, find the GCD for the integers 54 and 81 using prime factorization.To do this we first need to find the prime factorization for each integers.

54 = 2 x 3 x 3 x 3
81 = 3 x 3 x 3 x 3
 
Next, we write the factorizations, aligning each repeated factor vertically. The GCD is the product of the prime factors that appear in both factorizations.

                   54 = 2 x 3 x 3 x 3
                   81 =       3 x 3 x 3 x 3
GCD (54, 81) =          3 x 3 x 3

so, GCD (54, 81) = 3 x 3 x 3 = 27, which is the same number we found using the intersection of sets method.

A really useful tool for checking your work is the prime factorization calculator.

Example 3 - Euclidean Algorithm

The theorem of the Euclidean Algorithm states,

"Let a and b be any two natural number, with a > b. Divide a by b to get a remainder r.  If r = 0, then b = GCD(a,b), but if r > 0, divide b by r to get a remainder s.  If s = 0, then r = GCD(a,b), but if s > 0, divide r by s to get a remainder t.  Continue the division-with-remainder process until a remainder of 0 results.  Then the last nonzero remainder is GCD(a,b)."

The Euclidean algorithm works well for finding the GCD of larger numbers.  Find the GCD of 5672 and 28468.

28468/5672 = 5 R 108

5672/108 = 52 R 56

108/56 = 1 R 52

56/52 = 1 R 4

52/4 = 13

Therefore, the GCD(5672, 28468) = 4