Content

• Steps
• Method 1 of 2: Divider Algorithm
• Method 2 of 2: Prime Factors
• Tips

The Greatest Common Divisor (GCD) of two integers is the largest integer that divides each of those numbers. For example, the gcd for 20 and 16 is 4 (both 16 and 20 have large divisors, but they are not common - for example, 8 is a divisor of 16, but not a divisor of 20). There is a simple and systematic method for finding GCD, called "Euclid's algorithm". This article will show you how to find the greatest common divisor of two integers.

Steps

Method 1 of 2: Divider Algorithm

1. 1 Omit any minus signs.
2. 2 Learn the terminology: when dividing 32 by 5,
   • 32 - dividend
   • 5 - divisor
   • 6 - private
   • 2 - remainder
3. 3 Determine the larger of the numbers. It will be divisible, and the smaller number will be the divisor.
4. 4 Write down the following algorithm: (dividend) = (divisor) * (quotient) + (remainder)
5. 5 Put a larger number in the place of the dividend and a smaller number in the place of the divisor.
6. 6 Find how many times the greater number is divided by the lesser, and write the result instead of the quotient.
7. 7 Find the remainder and write it in the appropriate position in the algorithm.
8. 8 Write the algorithm again, but (A) write the previous divisor as a new dividend, and (B) the previous remainder as a new divisor.
9. 9 Repeat the previous step until the remainder is 0.
10. 10 The last divisor will be the greatest common divisor (GCD).
11. 11 For example, let's find the GCD for 108 and 30:
12. 12 Notice how the numbers 30 and 18 from the first line form the second line. Then 18 and 12 form the third row, and 12 and 6 form the fourth row. Multiples of 3, 1, 1, and 2 are not used. They represent the number of times the dividend is divisible and therefore unique to each row.

Method 2 of 2: Prime Factors

1. 1 Omit any minus signs.
2. 2 Find prime factors of numbers. Present them as shown in the picture.
   • For example, for 24 and 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • For example, for 50 and 35:
     • 50- 2 x 5 x 5
     • 35- 5 x 7
3. 3 Find common prime factors.
   • For example, for 24 and 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • For example, for 50 and 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Multiply the common prime factors.
   • For 24 and 18, multiply 2 and 3 and get 6... 6 is the greatest common denominator of 24 and 18.
   • There is nothing to multiply for 50 and 35. 5 Is the only common prime factor, and it is the GCD.
5. 5 Made!

Tips

• One way to write this is: dividend> mod divider> = remainder; GCD (a, b) = b if mod b = 0, and gcd (a, b) = gcd (b, a mod b) otherwise.
• As an example, let's find the GCD (-77.91). First, use 77 instead of -77: GCD (-77.91) converts to GCD (77.91). 77 is less than 91, so we have to swap them, but consider how the algorithm works if we don't. When calculating 77 mod 91, we get 77 (77 = 91 x 0 + 77). Since this is not zero, we consider the situation (b, a mod b), that is, GCD (77.91) = GCD (91.77). 91 mod 77 = 14 (14 is the remainder). It is not zero, so GCD (91.77) becomes GCD (77.14). 77 mod 14 = 7. This is not zero, so GCD (77.14) becomes GCD (14.7). 14 mod 7 = 0 (since 14/7 = 2 without a remainder). Answer: GCD (-77.91) = 7.
• The described method is very useful for simplifying fractions. In the example above: -77/91 = -11/13, since 7 is the greatest common denominator of -77 and 91.
• If a and b are equal to zero, then any nonzero number is their divisor, so in this case there is no GCD (mathematicians simply think that the greatest common divisor of 0 and 0 is 0).