| | |
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$.
The following shows this algorithm being applied to find $gcd(4269,3741)$:
4269 = 1 * 3741 + 528 3741 = 7 * 528 + 45 528 = 11 * 45 + 33 45 = 1 * 33 + 12 33 = 2 * 12 + 9 12 = 1 * 9 + 3 9 = 3 * 3 + 0 gcd(4269,3741) = 3
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$.