The GCD: greatest common divisor
What is the PGCD?
Divisors of a number
A divisor of an integer is a number that divides it exactly, leaving no remainder. For example, the divisors of 12 are: 1, 2, 3, 4, 6, 12.
Common divisors
When comparing two numbers, some divisors are common to both. Let’s take 12 and 18:
| Number | Divisors |
|---|---|
| 12 | 1, 2, 3, 4, 6, 12 |
| 18 | 1, 2, 3, 6, 9, 18 |
The common divisors of 12 and 18 are: 1, 2, 3, 6.
The GCD, the largest of them
The GCD (Greatest Common Divisor) is, as its name suggests, the largest of all the common divisors. Here, GCD(12, 18) = 6.
We note this: GCD(12, 18) = 6.
Why is it useful?
The GCD is used, for example, to:
- simplify a fraction as much as possible,
- divide objects into identical batches (the largest possible batch),
- solve problems involving fair division.
Common pitfall
Do not confuse the GCD (Greatest Common Divisor) with the LCM (Least Common Multiple). The GCD is always less than or equal to both original numbers, whereas the LCM is always greater than or equal to them.
Another pitfall: the GCD of two numbers is never equal to 0 (except in the special case where both numbers are zero, which is not relevant at secondary school level). It is at least 1 when the two numbers have no common divisors other than 1: we then say that they are relatively prime.