GCD (Greatest Common Divisor)
$$\gcd(a, b) = \gcd(b,\, a \bmod b)$$
What is GCD (Greatest Common Divisor)?
The GCD (Greatest Common Divisor) of two positive integers is the largest integer that divides both numbers exactly, leaving no remainder. It is also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF). GCD(12, 8) = 4 because 4 divides both 12 and 8 perfectly, and no integer larger than 4 does the same.
The most efficient method for finding the GCD is the Euclidean algorithm: divide the larger number by the smaller, take the remainder, and repeat until the remainder is zero. The last non-zero remainder is the GCD. Example: GCD(18, 24) - divide 24 by 18, remainder 6. Divide 18 by 6, remainder 0. GCD = 6.
In fraction arithmetic, the GCD is used to simplify (reduce) a fraction to its lowest terms. Dividing both numerator and denominator by their GCD produces an equivalent fraction where the two parts share no common factor other than 1.
GCD (Greatest Common Divisor) explained to a beginner
Imagine you have 12 apples and 8 oranges and want to arrange them into identical groups with no fruit left over. The largest number of equal groups possible is 4 - giving 3 apples and 2 oranges per group. That "4" is GCD(12, 8).
For fractions, the GCD tells you how much you can shrink the fraction without changing its value. 12/18 divided top and bottom by GCD(12, 18) = 6 gives 2/3 - the same fraction, at its smallest.
When to use GCD (Greatest Common Divisor)
Use the GCD to simplify fractions after addition, subtraction, or multiplication, and as an intermediate step when computing the LCM via LCM(a, b) = a × b ÷ GCD(a, b). Always check the GCD before reporting a fraction result to confirm it is fully reduced.
Worked examples for GCD (Greatest Common Divisor)
This table quickly gives you the overview you need to understand GCD (Greatest Common Divisor) and its most important comparisons.
| Numbers | GCD | Application |
|---|---|---|
| 12, 8 | 4 | 12/8 simplifies to 3/2 |
| 18, 24 | 6 | 18/24 simplifies to 3/4 |
| 7, 13 | 1 | Coprime: 7/13 is already in lowest terms |
| 100, 75 | 25 | 100/75 simplifies to 4/3 |
| 6, 9 | 3 | LCD(6,9) = 6×9÷3 = 18 |
Common pitfalls
GCD(a, b) = 1 means the numbers are coprime - the fraction is already in simplest form. This is not an error; it confirms no further reduction is possible. A common mistake is stopping at a common divisor that is not the greatest - dividing 18/24 by 2 gives 9/12, but the GCD is 6 and the fully reduced form is 3/4. Always verify you have found the greatest, not just a, common divisor.
Frequently asked questions about GCD (Greatest Common Divisor)
What is the difference between GCD and LCM?
GCD finds the largest shared factor (used to simplify fractions and compute LCD). LCM finds the smallest shared multiple (used to find a common denominator). They are linked: GCD(a, b) × LCM(a, b) = a × b, so knowing one gives you the other.
What does it mean when GCD equals 1?
When GCD(a, b) = 1, the numbers are coprime - they share no common factor other than 1. For a fraction, this means it is already fully reduced. For denominators, it means their LCD equals their product.
How do you find the GCD without the Euclidean algorithm?
List all factors of each number and find the largest one they share. For 12 and 8: factors of 12 are 1, 2, 3, 4, 6, 12; factors of 8 are 1, 2, 4, 8. Largest shared factor is 4. For large numbers the Euclidean algorithm is much faster.