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:
\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:
\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:
\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}