GCD and LCM

We say that $a$ divides $b$ (written $a \mid b$) when $b$ is a multiple of $a$:

Before hunting for common divisors it pays to know the divisibility rules — they spot a divisor without any dividing:

• by 2 — when the last digit is even,
• by 3 — when the digit sum is divisible by 3,
• by 4 — when the number formed by the last two digits is divisible by 4,
• by 5 — when the last digit is 0 or 5,
• by 9 — when the digit sum is divisible by 9,
• by 10 — when the last digit is 0.

Greatest common divisor

The GCD of two numbers is the largest number dividing both:

The simplest method is to list the divisors of both numbers and take the largest they share:

When $\gcd(a, b) = 1$ the numbers share no divisor beyond one — they are coprime. That happens for $8$ and $15$, for instance, even though neither of them is prime.

The Euclidean algorithm

Listing divisors gets unwieldy for larger numbers. A relation known for over two thousand years is far quicker:

Replace the pair by "the smaller number and the remainder" until the remainder hits zero. The last non-zero number is the GCD.

Lowest common multiple

The LCM is the smallest positive number divisible by both:

Multiples of $4$: $4, 8, \mathbf{12}, 16, 20, 24, \ldots$; multiples of $6$: $6, \mathbf{12}, 18, 24, \ldots$ — the first shared one is $12$, so $\operatorname{lcm}(4, 6) = 12$.

Nothing has to be listed, though, because the GCD and the LCM are tied together:

Why it matters

Both ideas come back with fractions: the GCD of the numerator and the denominator reduces a fraction to lowest terms, and the LCM of the denominators is the lowest common denominator when adding. Outside maths the LCM answers questions like "how often do both buses leave at the same time", and the GCD "how large can equal square tiles be to cover a rectangle without cutting".

Common mistakes

• Swapping the GCD and the LCM — the GCD is no larger than either number, the LCM no smaller; a result the other way round signals a slip.
• Taking the product as the LCM — $a \cdot b$ is a common multiple, but the lowest one only when the numbers are coprime.
• Stopping the Euclidean algorithm one step too late — the GCD is the last non-zero remainder, not the zero that ends the procedure.
• Assuming two composite numbers cannot be coprime — $8$ and $15$ are both composite, yet $\gcd(8, 15) = 1$.