Greatest Common Divisor

The greatest common divisor (or GCD) of two or more numbers is the largest number that exactly divides all.

Calculation of the Greatest Common Divisor

1. Decompose the numbers into prime factors.

2. Select the common factors with the smallest exponent.

Examples

Determine the GCD of: 72, 108 and 60:

1.

Factor Decomposition

72 = 23 · 32

108 = 22 · 33

60 = 22 · 3 · 5

2.

GCD (72, 108, 60) = 22 · 3 = 12

12 is the largest number that divides 72, 108 and 60.

If a number is a divisor of another, then this number is the GCD.

The number 12 is a divisor of 36.

GCD (12, 36) = 12