Greatest Common Factor (gcf)

Greatest Common Divisor (GCD) or Greatest Common Factor (GCF)

Example 1: Find Greatest Common Divisor of 150 and 54, ie GCD(150,54) Method 1 2 54 150 -108 42 1 previous remainder

42

previous divisor

54 -42 12

3 previous remainder

12

previous divisor

42 -36 6

GCD

2 previous remainder

6

12

previous divisor

-12 Stop when you get 0 remainder

0

The GCD is the second to last remainder. ∴ GCD(150, 54) = 6 Method 2 Take difference of 150 and 54: 150 - 54 = 96 For each step take the absolute difference of the previous result and smaller number, continue to do this until you get a zero. 96 - 54 = 42 54 - 42 = 12 42 - 12 = 30 30 - 12 = 18 18 - 12 = 6 12 - 6 = 6 ← GCD 6 - 6 = 0 (stop here)

1

∴ GCD(150,54) = 6 Example 2: Find Greatest Common Divisor of 28,42, and 126. Method 1 Compute the GCD using any two numbers from the set. Compute GCD(28,42). 1 28

42 -28 14

GCD

2 previous remainder

14

previous divisor

28 -28

stop when you get 0 remainder

0

GCD(28,42) = 14. Now compute the GCD of 14 and 126. 9 14

GCD

126 -126 0

As seen in this example, if you get a 0 remainder on first step, then the GCD is the divisor. GCD(14,126) = 14. ∴ GCD(28, 42, 126) = 14. Method 2 Just as with Method 1, we need to first find the GCD of two numbers from the set. Find GCD(28,42). 42 - 28 = 14 28 - 14 = 14 ← GCD 14 - 14 = 0 (stop here) GCD(28,42) = 14 Now, find GCD(14,126) 126 - 14 = 112 112 - 14 = 98 98 - 14 = 84 84 - 14 = 70 2

70 56 42 28 14

-

14 14 14 14 14

= = = = =

56 42 28 14 ← GCD 0 (stop here)

So, GCD of 14 and 126 = 14. ∴ GCD(28, 42, 126) = 14.

3