Greatest common divisor (GCD)

The greatest common divisor (GCD) of several numbers is the largest natural number that divides these numbers without remainder. For example, for the numbers 18 and 30, the greatest common divisor is 6; for the numbers 10, 15, 45, the greatest common divisor is 5.

Finding the greatest common divisor

To find the GCD of several numbers, you need:
1) factorize these numbers into prime factors;
2) mark those factors that are included in the expansion of all numbers;
3) find the product of the marked factors in the expansion of any of the given numbers.

Examples.

Example 1.
Find the greatest common divisor of numbers 48, 18, 16.
Solution.
Let us write out the prime factorizations for the given numbers and underline those factors that are included in the factorizations of all numbers:
48 = 2*2*2*2*3,

18 = 2*3*3,

16 = 2*2*2*2.
Therefore, GCD(48, 18, 16) = 2.
Answer: 2.

Example 2.
Find the greatest common divisor of numbers 120, 45, 150.
Solution.
Let us write out the prime factorizations for the given numbers and underline those factors that are included in the factorizations of all numbers:
120 = 2*2*2*3*5,

45 = 3*3*5,

150 = 2*3*5*5.
Therefore, GCD(120, 45, 150) = 3*5 = 15.
Answer: 15.

Example 3.
Find the greatest common divisor of numbers 324, 432.
Solution.
Let us write out the prime factorizations for the given numbers and underline those factors that are included in the factorizations of all numbers:
324 = 2*2*3*3*3*3,

432 = 2*2*2*2*3*3*3.
Therefore, GCD(324, 432) = 2*2*3*3*3 = 108.
Answer:108.

Example 4.
Find the greatest common divisor of numbers 48, 60, 80.
Solution.
Let us write out the prime factorizations for the given numbers and underline those factors that are included in the factorizations of all numbers:
48 = 2*2*2*2*3,

60 = 2*2*3*5,

80 = 2*2*2*2*5.
Therefore, GCD(48, 60, 80) = 2*2 = 4.
Answer: 4.

Euclidean algorithm for finding the greatest common divisor of two numbers

In addition to the specified method for finding the GCD of several numbers, there is the Euclidean algorithm for finding the greatest common divisor of two numbers a and b (a > b). It can be described as follows:
we get a chain of numbers a > b > r₁ > r₂ > r₃ > ... > r_n according to the formulas

a = b*q₀ + r₁, where r₁ is the remainder of dividing a by b;

b = r₁*q₁ + r₂, where r₂ is the remainder of dividing b by r₁;

r₁ = r₂*q₂ + r₃, where r₃ is the remainder of dividing r₁ by r₂;

...

r_n-2 = r_n-1*q_n-1 + r_n, where r_n is the remainder of dividing r_n-2 на r_n-1;

r_n-1 = r_n*q_n;

GCD(a,b) = r_n.

In other words, you need to find the remainders from dividing a larger number by a smaller one in this chain until you get zero as a remainder. The last divisor will be the GCD of the two numbers.

Examples.

Example 5.
Find the greatest common divisor of numbers 48, 18 using Euclidean algorithm.
Solution.
48 = 18*2 + 12; (48 divided by 18, the remainder is 12)

18 = 12*1 + 6; (18 divided by 12, the remainder is 6)

12 = 6*2; (12 divided by 6, the remainder is 0, the last divisor is the GCD).
Therefore, GCD(48, 18) = 6.
Answer: 6.

Example 6.
Find the greatest common divisor of numbers 126, 900 using Euclidean algorithm.
Solution.
900 = 126*7 + 18; (900 divided by 126, the remainder is 18)

126 = 18*7; (126 divided by 18, в остатке 0, the last divisor is the GCD)
Therefore, GCD(126, 900) = 18.
Answer: 18.

Example 7.
Find the greatest common divisor of numbers 495, 270 using Euclidean algorithm.
Solution.
495 = 270*1 + 225; (495 divided by 270, the remainder is 225)

270 = 225*1 + 45; (270 divided by 225, the remainder is 45)

225 = 45*5; (225 divided by 45, the remainder is 0, the last divisor is the GCD)
Therefore, GCD(495, 270) = 45.
Answer: 45.

The Euclidean algorithm can also be used if it is necessary to find the GCD of several numbers. To do this, you must first find the GCD of the first two numbers, then the GCD of the result and the third number, then the GCD of this result and the fourth number, etc. The last GCD obtained will be the answer.