Euclidean Algorithm/Demonstration

From ProofWiki
Jump to navigation Jump to search

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$


Sources