GCD and the Euclidean Algorithm

What is the largest integer that divides both 252 and 105?

You could list all divisors of each and find the intersection. That works here. It doesn't work when the numbers are large. You need a better question: is there a structure to shared divisors that lets you compute without listing?

There is. It's 2300 years old.

---

Divisibility, precisely

For integers $a$ and $b \neq 0$, we say $b$ divides $a$ — written $b \mid a$ — if there exists an integer $k$ such that $a = kb$.

Three facts do most of the work in this topic:

• If $d \mid a$ and $d \mid b$, then $d \mid a - b$.
• More generally: if $d \mid a$ and $d \mid b$, then $d \mid ma + nb$ for any integers $m, n$.
• This last one — divisibility is preserved under linear combinations — is the engine behind everything below.

---

GCD — what it is

The greatest common divisor $\gcd(a, b)$ is the largest positive integer that divides both $a$ and $b$.

Before computing anything, notice what this definition guarantees:

• $\gcd(a, 0) = a$, because every integer divides 0.
• $\gcd(a, a) = a$.
• $\gcd(a, b) = \gcd(b, a)$ — order doesn't matter.
• $\gcd(a, b) = \gcd(|a|, |b|)$ — sign doesn't matter.

The last special case worth naming: when $\gcd(a, b) = 1$, we call $a$ and $b$ coprime. They share no common factor larger than 1.

---

The key observation

Here is the fact that makes efficient computation possible:

$\gcd(a, b) = \gcd(b,\ a \bmod b)$

Why? The Division Algorithm says: for any integers $a$ and $b > 0$, there exist unique integers $q$ and $r$ with $0 \leq r < b$ such that $a = qb + r$.

Now let $d$ be any common divisor of $a$ and $b$. Then $d \mid a$ and $d \mid qb$, so $d \mid a - qb = r$. So $d$ divides both $b$ and $r$.

Run it backwards: any common divisor of $b$ and $r$ divides $qb + r = a$, so it divides both $a$ and $b$.

The set of common divisors of $(a, b)$ and $(b, r)$ are identical. Their maxima — the GCDs — must be equal.

---

The Euclidean Algorithm

Apply the observation repeatedly. At each step, replace the larger argument with the remainder. The remainders strictly decrease toward 0. When you hit 0, the last nonzero remainder is the GCD.

Example. $\gcd(252, 105)$:

$252 = 2 \times 105 + 42$ $105 = 2 \times 42 + 21$ $42 = 2 \times 21 + 0$

Answer: $\gcd(252, 105) = 21$.

Example. $\gcd(1071, 462)$:

$1071 = 2 \times 462 + 147$ $462 = 3 \times 147 + 21$ $147 = 7 \times 21 + 0$

Answer: $\gcd(1071, 462) = 21$.

---

How fast does it terminate?

Each step replaces $(a, b)$ with $(b, r)$ where $r < b$. The second argument strictly decreases. But how many steps?

The worst case is consecutive Fibonacci numbers. Watch what happens with $\gcd(F_{n+1}, F_n)$:

$F_{n+1} = 1 \cdot F_n + F_{n-1}$

Each step peels off exactly one Fibonacci number. After $n$ steps you reach $\gcd(F_2, F_1) = \gcd(1, 1) = 1$.

Since $F_n$ grows like $\phi^n$, the number of steps is at most $O(\log_\phi(\min(a,b)))$ — logarithmic in the input. Even for billion-digit numbers, the algorithm terminates in thousands of steps.

---

LCM — the companion

The least common multiple $\text{lcm}(a, b)$ is the smallest positive integer divisible by both $a$ and $b$.

The two quantities are linked:

$\gcd(a, b) \cdot \text{lcm}(a, b) = |a \cdot b|$

Proof. Let $d = \gcd(a, b)$. Write $a = dp$, $b = dq$ where $\gcd(p, q) = 1$.

Claim: $\text{lcm}(a, b) = dpq$.

$dpq$ is divisible by $a = dp$ and by $b = dq$. ✓

Now suppose $L$ is any common multiple of $a$ and $b$. Write $L = dpm$ for some integer $m$. Then $dq \mid dpm$ means $q \mid pm$. Since $\gcd(p, q) = 1$, we get $q \mid m$, so $L = dpqn \geq dpq$.

Therefore $\text{lcm}(a,b) = dpq$ and $\gcd(a,b) \cdot \text{lcm}(a,b) = d \cdot dpq = ab$. $\blacksquare$

Common mistake. This relation holds for two numbers only. $\gcd(a,b,c) \cdot \text{lcm}(a,b,c) \neq abc$ in general. Check with $a=b=c=2$.

---

Worked problems

Problem 1. If $\gcd(a, b) = 12$ and $\text{lcm}(a, b) = 1800$, find all pairs $(a, b)$ with $a \leq b$.

Write $a = 12p$, $b = 12q$ with $\gcd(p, q) = 1$. Then $\text{lcm}(a,b) = 12pq = 1800$, so $pq = 150 = 2 \times 3 \times 5^2$.

Coprime pairs $(p, q)$ with $p \leq q$ and $pq = 150$:

$p$	$q$	$\gcd(p,q)$
1	150	1 ✓
2	75	1 ✓
3	50	1 ✓
6	25	1 ✓
10	15	5 ✗

Pairs $(a, b)$: $(12, 1800)$, $(24, 900)$, $(36, 600)$, $(72, 300)$.

Problem 2. Find $\gcd(n, n+1)$ for any positive integer $n$.

Any common divisor $d$ satisfies $d \mid n$ and $d \mid n+1$, so $d \mid (n+1) - n = 1$. Thus $d = 1$.

Consecutive integers are always coprime.

Problem 3. Show that $\gcd(n, n+k) = \gcd(n, k)$.

$\gcd(n, n+k) = \gcd(n, (n+k) - n) = \gcd(n, k)$. The shift by $n$ is invisible.

---

What this page doesn't answer

The Euclidean Algorithm finds $\gcd(a, b)$. It doesn't tell you what $\gcd(a, b)$ is beyond "the largest common divisor." There's a deeper characterization — the GCD is the smallest positive integer expressible as a combination $ax + by$.

That's Bezout's Identity, and it's where the real power lives.