GCD



Use this calculator to :

Calculate GCD (or Greatest Common Divisor) of two, three or more integers.
Enter positive integers separated by spaces to calculate their GCD.

- Find common divisors. To find common divisors of two numbers, enter for example '81 900'. To find common divisors of three numbers, enter for example '90 81 12'.

What is GCD ?

The GCD of two integers is the Greatest Common Divisor of these two integers.

Example: What is GCD of 14 and 49 ?

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

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

How to calculate GCD ?

There are several methods to calculate GCD.

Method of divisors : This method simply applies the GCD definition.
- list the divisors of the two integers (e.g. using this calculator Find a number divisors).
- deduce the common divisors.
- The GCD is the largest common divisor.

Example: What is the 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. We deduce,
GCD (54.81) = 27

The above method is not recommended because it requires the calculation of all the divisors of the integers, which can be tedious for large numbers. The two below methods are faster.

Method of successive subtractions

This method follows this principle: if a number is a common divisor to two integers then it divides their difference.
Applied to the GCD of two integers a and b (which is a common divisor to a and b) this gives, the GCD (a, b) divides a - b.

To apply it to the same example (GCD of 54 and 81 ?), we calculate the difference between the 2 integers,
81 - 54 = 27
The process is repeated with the smallest number (54) and the calculated difference (27):
54 - 27 = 27
Once again, same process with the the smallest number (27) and the calculated difference (27):
27 - 27 = 0

the GCD is the last difference before getting 0. If we reach 1 then GCD = 1 (and the numbers are said coprime numbers).

GCD (81.54) = 27

Euclid Method

This method is the consequence of the Euclid lemma. This is the fastest way to find the GCD of two numbers.

To find the GCD of two numbers a and b, proceed in steps,

- Do the Euclidean division of a (the largest of the 2 integers) by b, we get a quotient q and a remainder r
- Repeat the same operation by replacing (a, b) with (b, r) until you get a zero remainder.
- The GCD (a, b) equals the last non-zero remainder

Example: What is the GCD of 54 and 81 ?

- 81 ÷ 54 = 1 remainder 27
- repeat the same operation by replacing a with b (= 54) and b with the remainder (= 27)
54 ÷ 27 = 2 remainder 0

The GCD = 27 (last remains non-zero).

Another example: What is the GCD of 544 and 88?

- 544 ÷ 88 = 6 remaining 16
- 88 ÷ 16 = 5 remainder 8
- 16 ÷ 8 = 2 remainder 0

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

Special Cases

- If b is a divisor of a, then the GCD of a and b is equal to b.
- If the 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.pgcd (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

This program computes the GCD of two integers.

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