# Euclidean Algorithm/Demonstration

## Example of use of Euclidean Algorithm

Using the Euclidean Algorithm, we can investigate in detail what happens when we apply the Division Theorem repeatedly to $a$ and $b$.

 $\ds a$ $=$ $\ds q_1 b + r_1$ $\ds b$ $=$ $\ds q_2 r_1 + r_2$ $\ds r_1$ $=$ $\ds q_3 r_2 + r_3$ $\ds \cdots$  $\ds$ $\ds r_{n - 2}$ $=$ $\ds q_n r_{n - 1} + r_n$ $\ds r_{n - 1}$ $=$ $\ds q_{n + 1} r_n + 0$

From the Division Theorem, we know that the remainder is always strictly less than the divisor.

That is, in $a = q b + r$:

$0 \le r < \size b$

So we know that:

$b > r_1 > r_2 > \ldots > r_{n - 2} > r_{n - 1} > r_n > 0$

So the algorithm has to terminate.

$\blacksquare$