Greatest Common Divisor and Euclid's Algorithm

Greatest Common Divisor

Definition

For integers $a$ and $b$ (not both zero), the greatest common divisor $\gcd(a, b)$ is the largest positive integer $d$ such that $d \mid a$ and $d \mid b$.

By convention, $\gcd(0, 0) = 0$.

Examples

• $\gcd(12, 18) = 6$
• $\gcd(17, 5) = 1$
• $\gcd(100, 0) = 100$

Coprimality

We say $a$ and $b$ are coprime or relatively prime if $\gcd(a, b) = 1$.

Properties of GCD

Symmetry

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

Absolute Value

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

If $a \mid b$

If $a \neq 0$ and $a \mid b$, then $\gcd(a, b) = |a|$.

Adding Multiples

For any integers $k, \ell$:

$\gcd(a, b) = \gcd(a - kb, b)$

This is the key insight behind Euclid’s algorithm.

Euclid’s Algorithm

The Key Lemma

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

Proof: Let $a = bq + r$ with $0 \leq r < b$.

Any common divisor of $a$ and $b$ divides $r = a - bq$.

Any common divisor of $b$ and $r$ divides $a = bq + r$.

Thus $\{d : d \mid a \land d \mid b\} = \{d : d \mid b \land d \mid r\}$.

Taking the maximum, $\gcd(a, b) = \gcd(b, r) = \gcd(b, a \bmod b)$.

The Algorithm

Euclid’s algorithm computes $\gcd(a, b)$ recursively:

function gcd(a, b):
    if b = 0:
        return a
    else:
        return gcd(b, a mod b)

Termination

The second argument strictly decreases at each step: $a \bmod b < b$.

Since $b \geq 0$ and the non-negative integers are well-ordered, the algorithm terminates.

Example

Compute $\gcd(48, 18)$:

Step	$a$	$b$	$a \bmod b$
1	48	18	12
2	18	12	6
3	12	6	0
4	6	0	—

$\gcd(48, 18) = 6$.

Bézout’s Identity

Statement

Theorem (Bézout’s Identity): For integers $a$ and $b$ (not both zero), there exist integers $x$ and $y$ such that:

$ax + by = \gcd(a, b)$

Extended Euclidean Algorithm

We compute $x$ and $y$ alongside the GCD by tracking linear combinations.

Example: Find integers $x, y$ with $48x + 18y = \gcd(48, 18) = 6$.

Working through Euclid’s algorithm:

• $48 = 2 \cdot 18 + 12$
• $18 = 1 \cdot 12 + 6$
• $12 = 2 \cdot 6 + 0$

Back-substituting:

• $6 = 18 - 1 \cdot 12$
• $6 = 18 - 1 \cdot (48 - 2 \cdot 18) = 3 \cdot 18 - 1 \cdot 48$

So $x = -1$ and $y = 3$ verify $48 \cdot (-1) + 18 \cdot 3 = -48 + 54 = 6$.

Euclid’s Lemma

Statement

Lemma (Euclid’s Lemma): If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

Proof

Suppose $p \nmid a$. Since $p$ is prime, $\gcd(p, a) = 1$.

By Bézout’s Identity, there exist $x, y$ with $px + ay = 1$.

Multiply by $b$: $pxb + aby = b$.

Since $p \mid ab$, we have $p \mid aby$. Clearly $p \mid pxb$.

Thus $p \mid (pxb + aby) = b$.

Multiplicativity of GCD

Statement

If $\gcd(b, c) = 1$, then:

$\gcd(a, bc) = \gcd(a, b) \cdot \gcd(a, c)$

Proof Sketch

Let $d_1 = \gcd(a, b)$ and $d_2 = \gcd(a, c)$.

Since $\gcd(b, c) = 1$ and $d_1 \mid b$, $d_2 \mid c$, we have $\gcd(d_1, d_2) = 1$.

Both $d_1$ and $d_2$ divide $a$, so $d_1 d_2$ divides $a$.

Both $d_1$ and $d_2$ divide $bc$ (since $d_1 \mid b$ and $d_2 \mid c$), so $d_1 d_2$ divides $bc$.

Thus $d_1 d_2 \mid \gcd(a, bc)$.

For the reverse, use Bézout’s identity with the coprimality assumptions.

---

Summary

• $\gcd(a, b)$ is the largest common divisor, defined for $a, b$ not both zero
• Key lemma: $\gcd(a, b) = \gcd(b, a \bmod b)$
• Euclid’s algorithm terminates by well-foundedness
• Bézout’s Identity: $ax + by = \gcd(a, b)$ for some $x, y$
• Euclid’s Lemma: if prime $p \mid ab$, then $p \mid a$ or $p \mid b$