The rule
gcd(a, b) is the largest whole number that divides both a and b with no remainder. There are two ways to find it.
With prime factors. Factorise the numbers into primes and take the primes they share, each to the lowest power it appears with.
With Euclid’s algorithm. Divide the larger number by the smaller and keep the remainder. Then divide the smaller number by the remainder, and carry on. When the remainder is 0, the last remainder that was not 0 is the answer. The algorithm needs no factorising, so it also works on large numbers.
Worked examples
gcd(84, 360) with prime factors. 84 = 2² · 3 · 7 and 360 = 2³ · 3² · 5. Shared are 2 and 3. The lowest power of 2 is 2², of 3 it is 3¹. gcd = 2² · 3 = 12.
The same with Euclid.
- 360 = 4 · 84 + 24
- 84 = 3 · 24 + 12
- 24 = 2 · 12 + 0
The last remainder that was not 0 is 12.
Simplifying a fraction. 84/360: divide numerator and denominator by the gcd, 12, to get 7/30, which cannot be simplified further.
gcd and lcm together. For two numbers, gcd(a, b) · lcm(a, b) = a · b. Here 12 · 2520 = 30,240 = 84 · 360, so the least common multiple is 2520.
The GCD calculator works it out for several numbers and shows both methods.
Common mistakes
- Taking the highest power. That gives the lcm, not the gcd. 2³ does not divide 84.
- Including primes only one number has. 5 is in 360 but not in 84, so 5 does not divide 84.
- Thinking there is no gcd. Two numbers with no prime in common have gcd = 1. They are called coprime.
Common questions
What is the difference between the gcd and the lcm?
The gcd is the largest number that goes into the numbers; it is at most as large as the smallest of
them. The lcm is the smallest number the numbers go into; it is at least as large as the largest of
them.
Why does Euclid’s algorithm work?
A number that divides both a and b also divides the remainder when a is divided by b, because the
remainder is a minus some number of b’s. The pairs (360, 84), (84, 24) and (24, 12) therefore have the
same common divisors, and the last pair shows them directly.
How do you find the gcd of three numbers?
Two at a time: gcd(a, b, c) = gcd(gcd(a, b), c). With prime factors, take the primes that appear in all
three, to the lowest power.