GCD

Answer

What is GCD ?

GCD of two numbers is the Greatest Common Divisor of these two numbers.

Example. What is GCD of 14 and 49?

divisors of 14 = 1, 2, 7, 14
divisors of 49 = 1, 7, 49

The common divisors to 14 and 49 are 1 and 7. GCD is the greatest of them. Therefore,
GCD (14, 49) = 7.

GCD is also known as Highest Common Divisor (HCF) or Highest Common Divisor (HCD).

How to calculate GCD ?

There are several methods to calculate GCD.

Method of divisors

This method simply applies GCD definition (or brute force method). It is applicable to find GCD of two or more numbers. Here are the steps to follow,
• List the divisors of numbers (you may use this calculator Find a number divisors).
• Extract the common divisors.
• GCD is the largest common divisor.

Example. What is GCD of 54 and 81?

divisors of 54 = 1, 2, 3, 6, 9, 18, 27, 54
divisors of 81 = 1, 3, 9, 27, 81

The list of common divisors of 54 and 81 is 1, 3, 9, 27
The largest number in this list is 27. So, GCD (54.81) = 27.

Except for small numbers, the brute force method is not recommended since it requires the calculation of all numbers divisors which can be long and tedious for large numbers.

Euclid's Method

This method, also called 'GCD by repeated divisions', is the consequence of the following property.

Given A, B, q and r four integers. If A = B.q + r then GCD(A , B) = GCD(B , r)

Euclid's method consist on applying this equality repeatedly with q et r being the quotient and rest of euclidean division of A by B.

To find GCD of A and B, proceed with the following steps,

• Do the Euclidean division of A (the largest of the two numbers) by B and get the quotient q and remainder r.
• Proceed in the same way by replacing (A, B) with (B, r) and get get q' and r' the quotient and rest of euclidean division of B by r.
• Proceed the same with (r,r') and repeatedly until you get a zero remainder.
• GCD (A , B) is equal to the last non-zero remainder.

Example. What is GCD of 544 and 88?

• 544 ÷ 88 = 6 reminder 16
• 88 ÷ 16 = 5 reminder 8
• 16 ÷ 8 = 2 reminder 0

In each step, we keep the calculated remainder in the previous step and the smallest number among the dividend and divisor. We repeat the process until the remainder falls to zero.

The last non-zero remainder is 8 so GCD (544, 88) = 8.

This method is the most recommended and fatest to find GCD of two numbers. It is not applicable for more than two numbers.

Factorization method

Let's take an example to illustrate this method. What is GCD of 3960 and 18900?

• We factorize the two numbers,

`3960 = 2^3*3^2*5*11` (factorize 3960)
`18900 = 2^2*3^3*5^2*7` (factorize 18900)

• We'll calculate GCD from its prime factorization since its prime factors are the common prime factors of 3960 and 18900.
Prime factors of 3960 are 2, 3, 5 and 11
Prime factors of 18900 are 2, 3, 5 and 7
Then, prime factors of GCD are 2, 3 and 5

Each GCD factor will be elevated to an exponent that is equal to the lowest exponents in the two numbers factorizations. So,
2 is elevated to exponent 2 (compare exponents 3 and 2 in `2^3` and `2^2`)
3 is elevated to exponent 2 (compare exponents 2 and 3 in `3^2` and `3^3`)
5 is elevated to exponent 1 (compare exponents 1 and 2 in `5^1` and `5^2`)

So, `GCD ( 3960 , 18900 ) = 2^2 * 3^2 * 5 = 180`

Method of repeated subtractions

This method is the consequence of the following principle. if p divides A and p divides B then p divides A - B.

So, GCD (A , B) divides A - B since GCD is a common divisor to A and B.

To calculate GCD of A and B (A > B), we apply this property repeatedly.

• First step. GCD (A , B) divides A - B
• Second step. GCD (A , B) divides A - B and GCD (A , B) divides B, so, it divides their difference A - B - B = A - 2×B
• We repeat this process until we get a zero difference. Let's take an example to be more concrete.

What is GCD of 72 and 32?

A=72  B=32

72 - 32 = 40  (A - B)
40 - 32 = 8
32 - 8 = 24
24 - 8 = 16
16 - 8 = 8
8 - 8 = 0

In each step, we calculate the difference between the previous step result and the smallest number of the two other numbers. The process ends when we get a zero difference.

GCD is the last non zero difference (here 8). GCD (72 , 32) = 8.

In case we reach 1 as difference then GCD = 1 (and the numbers are said coprime numbers).

This method does not apply to more than two numbers. Moreover, apart from small numbers, it can be long and tedious in some cases.

How to choose a method?

If one has to select a single method among the four methods, Euclid's method is the best and the fatest with the following nuances.

Case of two numbers
For small numbers, the 'divisors' and 'repeated subtractions' methods do the work.
For large numbers, Euclid's method is recommended.

Case of more than two numbers
Factorization method is recommended except for small numbers where the divisors method (or brute force) is easy to apply.

Special Cases

• If B is a divisor of A, then GCD of A and B is equal to B.
• If GCD of A and B is equal to 1, then A and B are said coprime numbers.

GCD Properties (Advanced)

A and B are two non-zero integers then,
• GCD (A , B) divides LCM (A , B) (Least Common Multiple).

• If we multiply A and B by the same positive integer k then their GCD is multiplied by k.
GCD (k.A , k. B) = k.GCD (A , B)

• The product of their GCD by their LCM is equal to the absolute value of their product. This can be written,
GCD (A , B) x LCM (A , B) = |A x B|

• If A and B are two integers and p a common divisor to A and B then, p divides GCD (A , B).

Programming

Python

def gcd (a, b):
	while b:
 		a, b = b, a%b
 	return a

See also

Find all divisors of a number
LCM (Least Common Multiple)
Euclidean Division