a bit of number theory: Greatest Common Divisor

We'll discuss one of the most ancient algorithm in the history of Number Theory. 

Problem Statement:
Given two positive integers \( M\) and \(N\), find the greatest integer \(D\) such that \(D\) divides both \(M\) and \(N\).

In case you have forgotten, here are a few examples:

• for \(M=10\), \(N=55\), the greatest common divisor \(D\) is \( 5\)
• for \(M=72\), \(N=64\), the greatest common divisor \(D\) is \( 8\)

For small \( (M,N) \), \(D\) can usually be easily found by trial and error (and sometimes by terror), but for large values of \( (M,N) \), while trying all integers less than M and N might work, it can be really slow and certainly we can do better than this.

An efficient algorithm to solve this problem hinges on the following observation:
Theorem 1:
For positive integers \(a,b,d\), if \(d\mid a\) and \(d \mid b\), then \(d\mid ax+by\) for any \(x,y \in \mathbb{Z}\).

Proof:
Directly substituting \(a = kd\) and \(b = ld\) shows that the claim indeed holds. \(\blacksquare\)

With this, we can devise an efficient algorithm due to Euclid:

Euclid(M,N)
Input: M,N are integers, \(M\geq N\)
Output: integer D, the greatest common divisor of M and N
Pseudo-code:
if \(N\)==0:
   return \(M\)
return Euclid(\(N\), \(M \pmod{N}\))

Convince yourself that this algorithm works.
Euclid(M,N) eventually terminates with \( D = xM + yN\) for some \(x,y\in \mathbb{Z}\).
We will prove that it indeed returns the greatest common divisor of M and N.

Theorem 2:
Given integers \(d,x,y,a,b\), if \(d = ax + by\) and \(d\) divides both \(a\) and \(b\), then \(d\) is the greatest common divisor of \(a\) and \(b\).

Proof:
Suppose that \(d\) is not the greatest common divisor of \(a\) and \(b\). Hence there is \(D\) where \(D > d\) such that \(D\) divides both \(a\) and \(b\). By Theorem 1, \(D \mid ax + by = d\), which implies that \(D \leq d\), a contradiction. Hence \(d\) must be the greatest common divisor of \(a\) and \(b\). \(\blacksquare\)

Finally, what is the running time of Euclid(M,N)? It is guaranteed that Euclid(M,N) will terminate after \(O(\log{N})\) recursive calls since each call reduces the size of either M or N by half, with each call performs a modular arithmetic which can be done in constant time. The claim below explains the upper bound to the recursive call.

Claim:
If \(M \geq N\), then \(M \pmod{N} < \frac{M}{2}\) 

Proof:
\(N\) can be either bigger or less than \(\frac{M}{2}\), so we have 2 cases to consider:
Case 1: \(N \leq \frac{M}{2}\)
Then we know for a fact that \(M \pmod{N} < N \leq \frac{M}{2}\).
Case 2: \(N > \frac{M}{2}\)
Here we have \( M \pmod{N} \equiv M-N \pmod{N}\) and since \(M-N < M - \frac{M}{2} = \frac{M}{2} < N\) we have \(M \pmod{N} = M-N < \frac{M}{2}\). \(\blacksquare\)

Here is an implementation in C:

/* Recursive greatest common divisor */
int gcd(int M, int N){
   if (N>M) return gcd(N, M);
   if (N==0) return M;
   return gcd(N, M%N);
}