Solution: Greatest Common Divisor

Naive solution

Here is the simplest, but terribly slow, way to compute the greatest common divisor:

---

 $GCD(a,b)$
 for d from min$(a,b)$ downto 1:
  if d divides both a and b:
   return d

---

For example, for a$= 10^9$ and b$= 10^9 + 1$, this algorithm will perform about $10^9$ divisions.

Stop and think: If you computed $GCD($a$,$ b$)$, could you immediately find $GCD($a$-$b$,$ b$)$?

A simple, but crucial idea, that will lead us to a much faster algorithm is suggested by the illustration below.

It shows that if both a and b are divisible by d, then so is a $-$ b. It turns out that the converse is also true.

Exercise break: Prove that $GCD($a$,$ b$)$ $=$ $GCD($a$-$b$,$ b ...