The GCD and the Euclidean Algorithm

The Euclidean Algorithm

Suppose we are curious about the greatest common divisor of two numbers $m$ and $n$ (without loss of generality, assume $m > n$). Note, if we divide $m$ by $n$, we can find a unique integer quotient $q$ and positive integer remainder $r$ such that:

$$m=qn + r \quad; \quad \quad 0 \leq r \lt n$$

Letting $d$ be any divisor of both $m$ and $n$, the above relationship forces us to conclude that $d \mid r$ as well. Of course, this must then also hold for the greatest common divisor of $m$ and $n$, which we denote by $d=gcd(m,n)$.

This is fortuitous, as we now have a "smaller" pair of integers, $n$ and $r$, that $gcd(m,n)$ also divides. Appealing to the same process again, we can then find a still "smaller" pair, and a "smaller" one after that, and so on... until we must ultimately terminate with a division where the remainder is zero.

This suggests the following algorithm:

To compute the greatest common divisor of two numbers $m$ and $n$, let $r_0 = m$ and $r_1 = n$. Now compute successive quotients and remainders according to the recursive relationship $$r_{i-1} = q_{i+1} \cdot r_i + r_{i+1}$$ for $i=0,1,2,\ldots$ until some remainder $r_j$ is zero. The last nonzero remainder found is then the greatest common divisor of $m$ and $n$.

A Recursive Definition for the GCD

There is another way we can think about this. Note, when $n \mid m$ we have $$\textrm{gcd}(m,n)=n$$ while otherwise, $$\textrm{gcd}(m,n)=\textrm{gcd}(n,\textrm{Mod}(m,n))$$ where $\textrm{Mod}(m,n)$ is the remainder of $m$ divided by $n$.