GCD & Euclidean Algorithm

Definition

Greatest Common Divisor

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

Examples: gcd(12, 18) = 6, gcd(17, 5) = 1, gcd(0, n) = n.

If gcd(a, b) = 1, we say a and b are coprime (or relatively prime).

Definition

Least Common Multiple

The least common multiple of a and b, written lcm(a, b), is the smallest positive integer that is a multiple of both a and b.

Key relationship: gcd(a, b) × lcm(a, b) = |a × b|.

Example: gcd(12, 18) = 6, lcm(12, 18) = 36. Check: 6 × 36 = 216 = 12 × 18. ✓

Theorem

The Euclidean Algorithm

The Euclidean algorithm computes gcd(a, b) efficiently by repeated division:

gcd(a, b) = gcd(b, a mod b)

Repeat until the remainder is 0. The last non-zero remainder is the GCD.

This is one of the oldest algorithms in mathematics (~300 BCE) and runs in O(log(min(a,b))) steps.

Example

Euclidean Algorithm Example

Compute gcd(252, 105):

252 = 105 × 2 + 42 105 = 42 × 2 + 21 42 = 21 × 2 + 0

The last non-zero remainder is 21, so gcd(252, 105) = 21.

Theorem

Extended Euclidean Algorithm

Bézout's Identity: For any integers a, b, there exist integers x, y such that: ax + by = gcd(a, b)

The extended Euclidean algorithm finds x, y by working backward through the Euclidean algorithm steps.

Example

Extended Euclidean Example

Find x, y such that 252x + 105y = gcd(252, 105) = 21.

From the Euclidean algorithm: 42 = 252 - 105 × 2 21 = 105 - 42 × 2

Back-substitute: 21 = 105 - (252 - 105 × 2) × 2 21 = 105 - 252 × 2 + 105 × 4 21 = 252 × (-2) + 105 × 5

So x = -2, y = 5. Check: 252(-2) + 105(5) = -504 + 525 = 21. ✓