Back to School - Recapping on Euclid’s Algorithm

Euclid’s algorithm for finding the greatest common divisor (GCD) between two integer numbers is a simple algorithm you typically learn in middle school. And yet, to my embarassment, I realized today that I never actually stopped to reflect on why it works.¹ This is what I intend to do here today.

Let \(m\) and \(n\) be two integers for which we would like to find the greatest common divisor. As per the fundamental theorem of arithmetic, we know that both \(m\) and \(n\) can be expressed as a product of prime numbers. Let \(M\) represent the set of primes making up \(m\), and \(e_m(p)\) represent the exponent for prime \(p \in M\) in \(m\)’s factorization, and let \(N\) and \(e_n(p)\) represent the same quantities for \(n\).

Let’s define sets \(G\) and exponents \(e_g(p)\) so that \(g = \gcd(m,n) = \prod_{p \in G} p^{e_g(p)}\). It should be clear that if \(g\) is the greatest common divisior between \(m\) and \(n\), then:

• \(G = M \cap N\);
• \(e_g(p) = \min\{e_m(p), e_n(p)\}\).

i.e., we just need to take the prime factorizations of \(m\) and \(n\), find the common primes, and then take the smallest exponent for each common prime to find the GCD.

The problem with this method is that it requires knowing the prime factorizations of \(m\) and \(n\), which is thought to be a computationally hard problem. Euclid’s algorithm gives us an efficient way of finding \(g\) without computing those. But how?

Basic algorithm. Let \(g = \gcd(m, n)\). Then it must be true that \(m = g \times r_m\) and \(n = g \times r_n\) for some integer-valued \(r_m\), \(r_n\) as \(g\) divides both \(m\) and \(n\).

If \(m = n\), then trivially \(\gcd(m, n) = m = n\). Now assume wlog that \(m > n\). Then the difference \(m^\prime = m - n = g \times (r_m - r_n)\) is also divisible by \(g\). What might not be obvious is that \(\gcd(m^{\prime}, n) = g\). To see why, suppose it were not so. This means there is some \(g^{\prime} > g\) such that \(g^{\prime} = \gcd(m^{\prime}, n)\). In other words, it means that \(m^{\prime} = g^{\prime} \times q_{m^\prime}\), but it also means that \(n = g^{\prime} \times q_n\) for some integer \(q_n\).

Since \(m^\prime = m - n\), we get that \(m = m^\prime + n = g^{\prime} \times q_{m^\prime} + g^{\prime} \times q_n = g^{\prime}(q_{m^\prime} + q_n)\). But \(g^{\prime} > g\), which would contradict the fact that \(g = \gcd(m, n)\), so we must have tht \(g^{\prime} = g\). \(\blacksquare\)

And this sets the basis for the algorithm: subtract the smallest from the largest number and iterate until you get two equal numbers, and you got your greatest common divisor. But this is not very efficient.

Improved algorithm. Assuming wlog that \(m > n\), we can write down \(m = nq + r\). From the result discussed earlier, it is clear that \(\gcd(r, n)\) must be \(g\) as we can get to \(r\) by subtracting \(n\) from \(m\) \(q\) times. This means we can reduce the number of steps much faster if instead of subtracting \(n\) from \(m\), we compute \(m^{\prime} = m\mod n = r\). The stopping condition then becomes \(m^{\prime} = 0\), at which point we return \(n\) as the \(\gcd\). A result from 1844 shows that, when implemented this way, Euclid’s algorithm has complexity \(O(\log \min\{m, n\})\).

The final algorithm looks like:

def gcd(m: int, n: int) -> int:
  while m != 0:
    if m < n:
      t = m
      m = n
      n = t  
    m = m % n
  return n