The greatest common divisor (GCF) of two whole numbers is the largest whole number that is a divisor (factor) of both. For example, the longest number dividing 20 and 16 is 4. In school, the “guess and check” method is commonly taught. Instead, this is a simple and systematic way to do this and always find the correct answer. This method is called "Euclid's algorithm". Let's call the two numbers "a" and "b".
Steps
Method 1 of 2: Use the Divider Algorithm
Step 1. Get rid of negative numbers
Step 2. Learn your vocabulary:
when you divide 32 by 5,
-
- 32 is the dividend
- 5 is the divisor
- 6 is the quotient
- 2 is the remainder.
Step 3. Identify the larger number of the two
That will be the dividend, and the smaller the divisor.
Step 4. Write this algorithm:
(dividend) = (divisor) * (quotient) + (remainder)
Step 5. Put the largest number in the dividend place, and the smallest number as the divisor
Step 6. Decide how many times the small number fits into the large number, and put that algorithm as the quotient
Step 7. Calculate the remainder, substitute it in the appropriate place in the algorithm
Step 8. Write the algorithm again, but now A) use the previous divisor as the dividend and B) use the remainder as the new divisor
Step 9. Repeat the steps until the remainder is zero
Step 10. The last divisor is the greatest common divisor
Step 11. Here is an example, where we are trying to find the greatest common divisor of 108 and 30:
Step 12. Notice how 30 and 18 change position on the second line
Then 18 and 12 on the third line, and 12 and 6 on the fourth line. The 3, 1, 1, and 2 that follow after the multiplication symbol do not reappear. They represent how many times the divisor fits in the dividend, so they are unique on each line.
Method 2 of 2: Use Prime Factors
Step 1. Eliminate any negative signs
Step 2. Find the prime factors of the numbers, and list them as shown below
-
Using 24 and 18 as an example:
- 24- 2 x 2 x 2 x 3
- 18- 2 x 3 x 3
-
Using 50 and 35 as an example:
- 50- 2 x 5 x 5
- 35- 5 x 7
Step 3. Identify all the common prime factors
-
Using 24 and 18 as an example:
-
24-
Step 2. x 2 x 2
Step 3.
-
18-
Step 2
Step 3. x 3
-
-
Using 50 and 35 as an example:
-
50- 2 x
Step 5. x 5
-
35-
Step 5. x 7
-
Step 4. Multiply the common factors together
-
In the case of 24 and 18, multiply the
Step 2
Step 3. to get
Step 6.. The 6 is the greatest common factor of 24 and 18.
-
In the case of 50 and 35, there is nothing to multiply.
Step 5. it is the only common factor, and therefore it is the largest.
Step 5. Finished
Advice
- One way to write this, using the notation mod = the remainder is that GCD (a, b) = b if a mod b = 0, and GCD (a, b) = GCD (b, a mod b) otherwise.
- Like, let's find the GCD (-77, 91). First let's use 77 instead of -77, so GCD (-77, 91) becomes GCD (77, 91). Now 77 is less than 91 so it needs to be changed, but let's see how the algorithm handles that if we don't. When we calculate 77 and 91, we get 77 (since 77 = 91 x 0 + 77). Since that is not a zero, we change (a, b) to (b, a mod b) and that gives us: GCD (77, 91) = GCD (91, 77). 91 mod 77 gives 14 (remember, that means 14 is the remainder). Since it is not zero, we change GCD (91, 77) to GCD (77, 14). 77 mod 14 gives 7 which is not zero, so we change GCD (77, 14) to GCD (14, 7). 14 mod 7 is zero, since 14 = 7 * 2 with no remainder, so we stop. And that means: GCD (-77, 91) = 7.
- This technique is very useful when you want to simplify fractions. For the example above, the fraction -77/91 reduces to -11/13 because 7 is the GCF of -77 and 91.
- If 'a' and 'b' are both zero, then any number other than zero divides them both, so technically there is no LCD in this case. Mathematicians often say that the GCF of 0 and 0 is 0, and that is the answer this method gets.