The Euclidean Algorithm
Given integers i and j we are looking for the largest integer d
which divides both i and j. When an integer d divides
integer i, that means that there is another integer s such that
and if d divides integer j, there is another integer t such that
Then we can see that d divides the difference between i and j
In fact, for any multiple of j, for instance aj, d divides
the difference between i and aj
This gives us a way of simplifying our task of actually finding
d.
After accepting the input i, j, we arrange things so that i is
larger than or equal to j. Then we use our integer division to
select the integer a to make i - aj
as small as possible, but not negative.
-
If i - aj is zero, the largest integer dividing i
and j is j.
In this case, the algorithm is done immediately.
- Else, if the diffence is not zero,
run the algorithm again on j and i - aj.
The answer for this integer pair will also be the answer
for the original integer pair i, j.
The d "hiding" inside of both i and j is also
inside of j and i - aj because we showed that
any d dividing i and j divides i - aj as well.
We run the algorithm again by calling the procedure object inside
the procedure object itself - we use recursion.
Since i - aj is
smaller than i, we re-instantiate the procedure object only
a finite number of times:
you just can't make integers smaller but positive forever!
So eventually, the first condition holds, the difference made
is zero, and the value of d just pops out like magic - it is
the j value at the level of recursion for which
i-aj=0.