Common Ground: Part One

What the greatest common divisor and least common multiple have in common

You probably learned about greatest common divisors (GCD) and least common multiples (LCM) in school. GCD and LCM are some of the oldest ideas in number theory, and they go way deeper than you might expect. They sit beneath modern cryptography, networking, compilers, elliptic curves, planetary orbits, etc!

This is the first part in a 3-part series I'm doing on GCD and LCM.

In this post, Part 1, we will

• Define GCD and LCM
• Show how they relate
• Extend them to arbitrary lists of integers (n-ary $\mathrm{gcd}$ and $\mathrm{lcm}$)

In Part 2, we will go over Euclid's Extended Algorithm and its many applications to modern computing. In Part 3, we will extend the definitions of $\mathrm{gcd}$ and $\mathrm{lcm}$ to the rationals.

A quick note on style—I'll use "GCD" and "LCM" to refer to actual numbers, the results of the computations. I'll use $\mathrm{gcd}$ and $\mathrm{lcm}$ to refer to the functions, the computations themselves.

Greatest Common Divisor

The greatest common divisor (GCD) between two non-negative integers is the largest number that divides both evenly, usually written as $\mathrm{gcd}(x, y)$ for two non-negative integers $x$ and $y$.

Examples

Prime Factorization

The (arguably) simplest way to calculate GCD is to take the prime factors of each number and multiply together the prime factors they have in common.

Example

• $\mathrm{gcd}(18, 24)$
• Prime factors of $18$: $2, 3, 3$
• Prime factors of $24$: $2, 2, 2, 3$
• Prime factors in common: $2, 3$
• GCD = $2 \cdot 3 = 6$

This is really only useful for small numbers. There's not even an algorithm for efficiently ³ computing prime factors!

Euclid's Algorithm

There's no simple formula to calculate $\mathrm{gcd}$ for arbitrary numbers, you have to use an algorithm. ⁴

Luckily, Euclid has us covered. He described his titular algorithm in The Elements, where he used it to compute the GCD of line segments.

It goes like this: subtract the smaller number from the larger. Repeat until both numbers are the same.

Example

• $\mathrm{gcd}(100, 150)$
• $150 - 100 = 50$, so $\mathrm{gcd}(100, 150) = \mathrm{gcd}(100, 50)$
• Now, subtract the smaller from the larger again: $100 - 50 = 50$
• This tells us that $\mathrm{gcd}(100, 150) = \mathrm{gcd}(100, 50) = \mathrm{gcd}(50, 50)$
• Since both numbers are the same, we stop there. $50$ is the GCD.

Code

def gcd(a: int, b: int) -> int:
  a, b = abs(a), abs(b)

  while a != b:
    if a > b:
      a = a - b
    else:
      b = b - a

  return a

Or recursively:

def gcd(a: int, b: int) -> int:
  a, b = abs(a), abs(b)

  if a == b: return a
  if a > b: return gcd(a - b, b)
  return gcd(a, b - a)

Euclid's Algorithm via Remainders

Iterated subtraction is slow—worst-case, you subtract one number from the other again and again. That gives us an algorithm that runs in roughly proportional time to the size of the smaller number, $O(\min(a,b))$.

Instead, we can take remainders. Each remainder shrinks the numbers dramatically, giving us an $O(\log \min(a, b))$ algorithm—exponentially faster in practice.

Example

• $\mathrm{gcd}(24, 36)$
• $36\mod24 = 12$
• Then, $\mathrm{gcd}(24, 36) = \mathrm{gcd}(24, 12)$
• $24\mod12 = 0$
• Then, $\mathrm{gcd}(24, 12) = \mathrm{gcd}(0, 12)$
• $12$ is the GCD

Code

def gcd(a: int, b: int) -> int:
  a, b = abs(a), abs(b)

  while a != 0 and b != 0:
    if a > b:
      a = a % b
    else:
      b = b % a

  return a + b # One of a or b must be zero

I wrote like this, because it's easier to see what's happening. However, this algorithm has a shorter and more canonical form:

def gcd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

The greater than check was unnecessary. Do you see why?

Say we're on the first iteration of the loop and b > a. In that case, a % b == a, so the assignment a, b = b, a % b just swaps the two numbers: (a, b) becomes (b, a). Now a is the larger one, and on the next iteration we take the remainder of the larger divided by the smaller. No if statements needed!

In other words, the algorithm naturally orients the numbers so the remainder step is always reducing the larger number—no branch needed. The math enforces the flow.

Each iteration stores the smaller remainder in b. Eventually, the remainder hits zero, which means division was exact. At that moment, a holds the last non-zero value, the GCD.

Least Common Multiple

The LCM of two non-negative integers, $a$ and $b$, is the smallest number that is a multiple of both.

Examples

Prime Factorization

LCM can be expressed as prime factors of its arguments just like GCD. But where GCD is equal to the intersection of the prime factors, LCM is equal to the union of the prime factors divided by the intersection (i.e., the GCD).

Also, note that we're talking about multisets here, not normal mathematical sets.

Example

• $\mathrm{lcm}(18, 24)$
• Prime factors of $18$: $2, 3, 3$
• Prime factors of $24$: $2, 2, 2, 3$
• Union of prime factors: $2, 2, 2, 2, 3, 3, 3$
• Intersection of prime factors: $2, 3$
• $2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 = 432$
• GCD = $2 \cdot 3 = 6$
• LCM = $432 \div 6 = 72$

Again, not particularly useful, but it's an interesting number theory fact to be aware of.

The Formula in Terms of GCD

The cool thing about $\mathrm{lcm}$ is that it can be expressed as a simple formula based on $\mathrm{gcd}$:

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

The Relationship

The largest that the LCM of two integers, $x$ and $y$, can ever be is $x \cdot y$. This is the case when $x$ and $y$ are coprime.

What if they're not coprime? Take $lcm(20, 30)$. $20 \cdot 30 = 600$. But $600$ is not the LCM of $20$ and $30$. Since $20$ and $30$ are both divisible by $5$, we could divide $600$ by $5$ to get $120$. $120$ is indeed a common multiple of $20$ and $30$, but it's not the least common multiple, because $5$ is not the largest number that divides both $20$ and $30$.

What is the largest number that divides both $20$ and $30$? The GCD! In this case, it's $10$. Take the maximum, $600$ and divide it by $10$ to get $60$. $60$ is the LCM.

Thus, our formula:

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

Code

Given gcd:

def lcm(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    g = gcd(a, b)
    return 0 if g == 0 else (a * b) // g

n-ary LCM/GCD

$\mathrm{gcd}$ and $\mathrm{lcm}$ over the integers are commutative: $\mathrm{gcd}(a, b) = \mathrm{gcd}(b, a)$ (we used this property in the code for Euclid's Algorithm Via Remainders). They are also associative: $\mathrm{gcd}(\mathrm{gcd}(a, b), c) = \mathrm{gcd}(a, \mathrm{gcd}(b, c))$. We can use these properties to apply both $\mathrm{gcd}$ and $\mathrm{lcm}$ to lists of integers.

Code

def gcdn(*args: int) -> int:
  if not args: raise ValueError('Must provide at least one arg')

  res = args[0]
  for i in args[1:]:
    res = gcd(res, i)

  return res

If functional is your thing:

from functools import reduce
def gcdn(*args: int) -> int:
    if not args: raise ValueError('Must provide at least one arg')
    return reduce(gcd, args)

Note that folding (reducing) works here because $\mathrm{gcd}$ and $\mathrm{lcm}$ are associative, while idempotence ensures repeated values don't explode the computation.

That is,

• $\mathrm{gcd}(a,a)=a$
• $\mathrm{lcm}(a,a)=a$

The code for $\mathrm{lcm}$ is nearly identical. Just substitute the call to gcd with lcm.

Conclusion

In this post, we defined $\mathrm{gcd}$ and $\mathrm{lcm}$, showed how they are related to one another, and defined an n-ary version of both.

Coming Soon

• Part 2—The Extended Euclidean Algorithm, Modular Inverses, the Chinese Remainder Theorem, and applications to cryptography
• Part 3—Generalizing GCD and LCM to the Rationals

Athena Math

If you're weird like me, and you wanna practice calculating GCD and LCM mentally, there's only one app that I know that offers that: Athena Math.