The Euclidean Algorithm

The Euclidean Algorithm

On The Division Algorithm for Positive Integers we noted that for any positive integers $a$ and $b$ where $b \neq 0$ there exists unique integers $q$ and $r$ where $0 \leq r < b$ such that:

(1)
\begin{align} \quad a = bq + r \end{align}

We also looked at a lemma which stated that $(a, b) = (b, r)$.

Using both of these results, we will now see how the division algorithm can be applied successively to find the greatest common divisor between $a$ and $b$.

Theorem 1 (The Euclidean Algorithm): If $a$ and $b$ are positive integers where $b \neq 0$ then the greatest common divisor $r_t$ can be obtained by successively applying the division algorithm:
$a = bq + r \quad 0 \leq r < b \\b = rq_1 + r_1 \quad 0 \leq r_1 < r \\r = r_1q_2 + r_2 \quad 0 \leq r_2 < r_1 \\... \\ r_n = r_{n+1}q_{n+2} + r_{n+2} \quad 0 \leq r_{n+2} < r_{n+1}$
for which eventually $r_{t-1} = r_tq_{t+1}$ and $(a , b) = r_t \: t \in \mathbb{Z}$
  • Proof: Consider the following set of inequalities:
(2)
\begin{align} a = bq + r \quad 0 \leq r < b \\b = rq_1 + r_1 \quad 0 \leq r_1 < r \\r = r_1q_2 + r_2 \quad 0 \leq r_2 < r_1 \\... \\ r_n = r_{n+1}q_{n+2} + r_{n+2} \quad 0 \leq r_{n+2} < r_{n+1} \end{align}
  • We get that:
(3)
\begin{equation} 0 = ... < r_{n+2} < ... < r2 < r1 < b \end{equation}
  • This is a decreasing sequence of positive integers which must terminate at some $r_{t-1}$ to which $r_{t-1} = r_tq_{t+1}$ and such that:
(4)
\begin{align} \quad (a , b) = (b , r) = (r, r_1) = (r_1 , r_2) = ... = (r_{t-1} , r_{t}) = r_t \quad \blacksquare \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License