their HCF, the highest common factor. This is the largest number that divides both exactly. It is also called the GCD, the greatest common divisor. Same thing, two names. HCF of 12 and 18 is 6.
their LCM, the least common multiple. This is the smallest number that both divide exactly. LCM of 12 and 18 is 36.
HCF simplifies fractions. \frac{12}{18}: divide top and bottom by their HCF, 6, and you get \frac{2}{3}.
LCM answers "when do two repeating things line up again?" One bus comes every 12 minutes and another every 18 minutes. Both leave the station now. They next leave together after 36 minutes, the LCM. It is also the common denominator you use to add \frac{1}{12} + \frac{1}{18}.
At school you factorise both numbers into primes, using the loop from 4.0.5.
12 = 2^2 \times 3 \qquad 18 = 2 \times 3^2
The HCF takes each prime with its smaller power: 2^1 \times 3^1 = 6. The LCM takes each prime with its larger power: 2^2 \times 3^2 = 36.
This is correct, and it explains what HCF and LCM really are. But factorising costs O(\sqrt{n}) steps per number. For numbers near 10^{18} that is a billion steps. Euclid found a far faster way.
Any number that divides both a and b also divides a - b.
Why? Say d divides both. Then a = d \times x and b = d \times y for some whole numbers x and y. So a - b = d \times (x - y), which is also a multiple of d.
It works the other way too. Anything that divides both b and a - b also divides their sum, which is a. So the pair (a, b) and the pair (a - b, b) have exactly the same common divisors. That means they have the same HCF. But the second pair is smaller.
So keep replacing the larger number with the difference. When the two become equal, that value is the HCF.
python
def hcf_subtract(a: int, b: int) -> int: while a != b: if a > b: a -= b else: b -= a return aprint(hcf_subtract(12, 18)) # → 6
The pairs go (12, 18) \to (12, 6) \to (6, 6). The answer is 6.
The problem with subtraction. For hcf_subtract(1_000_000, 1) it subtracts 1 nearly a million times. All those subtractions of the same number are really one division. The remainder after dividing is exactly what you get after subtracting as many times as fits.
Replace "subtract b again and again" with "take the remainder after dividing by b".
\gcd(a, b) = \gcd(b,\ a \bmod b)
Read it aloud: "the HCF of a and b equals the HCF of b and the remainder of a divided by b." When the second number reaches 0, the first number is the answer. Why does 0 end it? Every number divides 0, since 0 = d \times 0. So the HCF of x and 0 is just x.
python
def hcf(a: int, b: int) -> int: while b != 0: # (1) a, b = b, a % b # (2) return a # (3)print(hcf(12, 18)) # → 6print(hcf(1071, 462)) # → 21print(hcf(17, 5)) # → 1
(1) Keep going until the remainder is 0.
(2) The new pair is (old b, remainder). This uses the tuple swap from 4.0.1. Both new values are computed from the old pair before either is stored.
(3) When b is 0, a holds the HCF.
You do not need a >= b to start. If a is smaller, the first step gives a % b = a, and the pair simply swaps. For hcf(12, 18): (12, 18) \to (18, 12) \to (12, 6) \to (6, 0). The answer is 6.
Trace on 1071 and 462:
a
b
a % b
1071
462
147
462
147
21
147
21
0
21
0
stop
The HCF is 21. Check: 1071 = 21 \times 51 and 462 = 21 \times 22.
How fast is it? Every two steps, the larger number at least halves. Here is why. Take a \bmod b. If b is at most half of a, the remainder is smaller than b, so it is below half of a. If b is more than half of a, then b fits once and the remainder is a - b, which is again below half of a. Halving every two steps means about 2 \log_2 n steps at most. For numbers near 10^{18}, that is under 130 steps.
Learn two HCF facts by heart. Two numbers with HCF 1 are called coprime. 17 and 5 are coprime. And the slowest inputs for Euclid are neighbouring Fibonacci numbers, like 89 and 55, because each remainder is the Fibonacci number just below.
The recursive version is the same rule written as a function that calls itself.
python
def hcf_rec(a: int, b: int) -> int: return a if b == 0 else hcf_rec(b, a % b)print(hcf_rec(48, 180)) # → 12
Here is the link between the two. For any two positive numbers:
a \times b = \text{HCF}(a, b) \times \text{LCM}(a, b)
Why? Look at the prime powers again. For each prime, the HCF takes the smaller power and the LCM takes the larger. Smaller plus larger always equals the two powers added together, which is exactly what a \times b has. For 12 and 18 and the prime 2: the powers are 2 and 1. HCF takes 1, LCM takes 2, and 1 + 2 = 3, which is the power of 2 in 12 \times 18 = 216 = 2^3 \times 3^3.
So the LCM is the product divided by the HCF.
python
def lcm(a: int, b: int) -> int: return a // hcf(a, b) * b # (1)print(lcm(12, 18)) # → 36print(lcm(4, 6)) # → 12
(1) Divide before multiplying. a * b // hcf(a, b) gives the same answer, but a * b can be huge. In Python that only costs time. In Java or C it overflows and gives a wrong answer. Dividing first keeps every middle value no bigger than the answer.
Zero.\gcd(a, 0) = a, since every number divides 0. \text{lcm}(a, 0) is defined as 0. Our lcm would compute 0 // hcf(0, b) * b. hcf(0, b) is b, so that is 0 // b * b = 0. Correct. But lcm(0, 0) divides by zero. Guard it if zeros are possible.
Negative numbers. HCF is usually defined as positive. Pass abs(a) and abs(b).
HCF: O(\log \min(a, b)) time, O(1) memory. LCM: the same, plus one division and one multiplication. For a list of n numbers: O(n \log M), where M is the largest value.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"Why does Euclid's method work?" Any number that divides both a and b also divides the remainder of a divided by b. So the pair (a, b) and the pair (b, a \bmod b) have the same common divisors. The second pair is smaller, so you keep going until the remainder is 0.
"How fast is it?" Very fast. Every two steps, the bigger number is at least cut in half. So it takes about 2 \log_2 n steps. For numbers near 10^{18}, that is under 130 steps.
"How do you get the LCM?" Use HCF × LCM = a \times b. So LCM = a // hcf(a, b) * b. Divide first and multiply second, so the middle value never gets too big.
"How do you find the HCF of a whole list?" Find the HCF of the first two numbers. Then the HCF of that answer with the third number. Continue to the end. If the answer ever becomes 1, you can stop early.
"Find the GCD of two strings." This is LeetCode 1071. First check s1 + s2 == s2 + s1. If not, there is no answer. If yes, the answer is the first \gcd(\text{len}(s1), \text{len}(s2)) characters of s1.
One thing to volunteer: "Euclid's method is over 2,300 years old, and computers still use it today."