The Euclidean Algorithm

Appendix A The Euclidean Algorithm

The Euclidean algorithm is a useful tool for finding the greatest common divisor of two non-zero integers, \(b \lt a\text{.}\) It is predicated on the fact that we can always find an integer, \(q\text{,}\) so that

\begin{equation*} 0 \leq r = a - qb \lt b \end{equation*}

🔗

Example A.1.

For integers \(a = 1234\) and \(b = 56\text{,}\) we can perform long division

\begin{align*} 56\overset{\phantom{)12}22}{\overline{\smash{)}{1234}}} \amp\\ \underline{-112}\phantom{4} \amp\\ 114 \amp\\ \underline{-112} \amp\\ 2 \amp \end{align*}

to see that \(1234 = (22)56 + 2\text{;}\) that is, \(q = 22\) and \(r = 2\text{.}\)

🔗

The Euclidean algorithm iterates this process until the remainder is eventually zero:

\begin{align*} a \amp= q_0 b + r_0\\ b \amp= q_1 r_0 + r_1\\ r_0 \amp= q_2 r_1 + r_2\\ \phantom{r_0} \amp\phantom{=} \vdots\\ r_{n-2} \amp = q_{n} r_{n-1} + r_{n}\\ r_{n-1} \amp = q_{n+1} r_{n-1} \end{align*}

🔗

Example A.2.

The Euclidean algorithm with the integers \(a = 16421\) and \(b = 7543\) yields the sequence

\begin{align*} 16421 \amp = (2)7543 + 1335\\ 7543 \amp = (5)1335 + 868\\ 1335 \amp = (1)868 + 467\\ 868 \amp = (1)467 + 401\\ 467 \amp = (1)401 + 66\\ 401 \amp = (6)66 + 5\\ 66 \amp = (13)5 + 1\\ 5 \amp = (5)1 + 0 \end{align*}

🔗

The Euclidean algorithm is a useful device for computing the greatest common divisor of two integers. To see this, we need a couple preliminary results.

🔗

Lemma A.3.

Assume \(a,b,c,x,y \in \Z\text{.}\) If \(a \mid b\) and \(a \mid c\text{,}\) then \(a \mid (bx + cy)\text{.}\)

🔗

Proof.

By the definition of divisibility, there exist integers \(\ell, k\) such that \(b = a\ell\) and \(c = ka\) so that

\begin{equation*} bx + cy = (a\ell)x + (ka)y = a(\ell x + ky) \end{equation*}

implies \(a \mid (bx + cy)\text{.}\)

🔗

Lemma A.4.

If \(a,b,q,r\) are integers that satisfy \(a = bq + r\text{,}\) then the greatest common divisor of \(a\) and \(b\) is the greatest common divisor of \(b\) and \(r\text{.}\)

🔗

Proof.

Let \(g\) be the greatest common divisor of \(a\) and \(b\) and let \(g^\prime\) be the greatest common divisor of \(b\) and \(r\text{.}\) Since \(g \mid a\) and \(g \mid b\text{,}\) Lemma A.3 implies that \(g\) is a divisor of

\begin{equation*} b(-q) + a = a - bq = r. \end{equation*}

Hence \(g\) is a divisor of \(b\) and \(r\text{.}\) By maximality of \(g^\prime\) amongst divisors of \(b\) and \(r\text{,}\) it follows that \(g \leq g^\prime\text{.}\)

🔗

On the other hand, since \(g^\prime \mid b\) and \(g^\prime \mid r\text{,}\) Lemma A.3 implies that \(g^\prime\) is a divisor of

\begin{equation*} q(b) + r = bq + r = a. \end{equation*}

Maximality of \(g\) implies that \(g^\prime \leq g\text{.}\) Since \(\leq\) is anti-symmetric, it follows that \(g = g^\prime\text{,}\) as desired.

🔗

Proposition A.5.

For non-zero integers \(b \lt a\text{,}\) the Euclidean algorithm terminates and the final non-zero remainder, \(r_n\text{,}\) is the greatest common divisor of \(a\) and \(b\text{.}\)

🔗

Proof.

To see the Euclidean algorithm terminates, it is enough to observe that the remainders

\begin{equation*} b > r_0 > r_1 > r_2 > \cdots \end{equation*}

form a decreasing sequence of integers, hence must eventually be zero.

🔗

Now that we know the algorithm terminates, the second claim follows from finitely many applications of Lemma A.4. Indeed, if the last non-zero remainder is \(r_n\)

then we obtain the chain of equalities

\begin{align*} \operatorname{gcd}(a,b) \amp= \operatorname{gcd}(b,r_0)\\ \amp = \operatorname{gcd}(r_0,r_1)\\ \amp = \operatorname{gcd}(r_1,r_2)\\ \amp \phantom{=}\vdots\\ \amp = \operatorname{gcd}(r_{n-2},r_{n-1})\\ \amp = \operatorname{gcd}(r_{n-1},r_{n})\\ \amp = \operatorname{gcd}(r_{n},0)\\ \amp = r_n. \end{align*}

Therefore \(\operatorname{gcd}(a,b) = r_n\text{,}\) the last non-zero remainder in the Euclidean algorithm.

🔗

Corollary A.6.

Assume \(a\) and \(b\) are non-zero integers. If \(g = \operatorname{gcd}(a,b)\text{,}\) then there exist integers \(x\) and \(y\) satisfying \(ax + by = g\text{.}\)

🔗

Proof.

Let \(g = \operatorname{gcd}(a,b)\text{.}\) We find \(x\) and \(y\) recursively using back-substitution in the Euclidean algorithm. We start by rewriting \(x_0 = 1\) and \(y_0 = -q_0\) so that

\begin{align*} r_0 \amp = a + (-q_0)b = x_0a + y_0b\\ r_1 \amp = b + (-q_1)r_0 \\ \amp = b + (-q_1)(x_0a + y_0)b\\ \amp = (-q_1x_0)a + (1 - q_0y_0)b. \end{align*}

Take \(x_1 = -q_1x_0\) and \(y_1 = 1 - q_0y_0\text{,}\) so that

\begin{equation*} r_1 = x_1 a + y_1 b. \end{equation*}

🔗

Now assume that for some \(k > 2\) we have written \(r_i = x_ia + y_ib\) for each \(0 \leq i \lt k\text{.}\) From the Euclidean Algorithm we have

\begin{align*} r_{k-2} = q_kr_{k-1} + r_k \amp \iff r_k = r_{k-2} - q_kr_{k-1}\\ \amp \iff r_k = (x_{k-2}a + y_{k-2}b) + (-q_k)(x_{k-1}a + y_{k-1}b)\\ \amp \iff r_k = (x_{k-2} - q_kx_{k-1})a + (y_{k-2} - q_kq_{k-1})b. \end{align*}

so if \(x_k = x_{k-2} - q_kx_{k-1}\) and \(y_k = y_{k-2} - q_kq_{k-1}\text{,}\) then

\begin{equation*} r_k = x_ka + y_kb. \end{equation*}

Since \(r_n = g\) is the greatest common divisor of \(a\) and \(b\text{,}\) it follows that there exist \(x,y \in \Z\) such that \(r_n = ax + by\) by induction.

🔗

Example A.7.

Using \(a = 16421\) and \(b = 7543\text{,}\) we can rewrite each expression in terms of the remainders

\begin{align*} 16421 = (2)7543 + 1335 \amp \iff 1335 = a - 2b\\ 7543 = (5)1335 + 868\amp \iff 868 = b - (5) 1335 = -5a +11b\\ 1335 = (1)868 + 467\amp \iff 467 = 1335 - 868 = 6a - 13b\\ 868 = (1)467 + 401\amp \iff 401 = 868 - 467 = -11a + 24b\\ 467 = (1)401 + 66\amp \iff 66 = 467 - 401 = 17a -37b\\ 401 = (6)66 + 5\amp \iff 5 = 401 - (6)66 = -113a + 246b\\ 66 = (13)5 + 1\amp \iff 1 = 66 - (13)5 = 1486a - 3235b \end{align*}

so that \(1486a + (-3235)b = 1\text{.}\)

🔗

This result is often useful in making divisibility arguments, which will be important when we discuss orders of elements later. The first result we prove characterizes integers with no common factors.

🔗

Definition A.8.

Two integers \(a,b \in \Z\) are coprime if the greatest common divisor of \(a\) and \(b\) is \(1\text{.}\)

🔗

Proposition A.9.

For all \(a,b \in \Z\text{,}\) \(a\) and \(b\) are coprime if and only if there exist \(x,y \in \Z\) such that \(ax + by = 1\text{.}\) Assume \(a,b \in \Z\text{.}\)

🔗

Proof.

Let \(g = \operatorname{gcd}(a,b)\text{.}\) If \(g = 1\text{,}\) then there exist \(x,y \in \Z\) such that \(ax + by = 1\) by Corollary A.6.

🔗

Conversely, assume \(d\) is a common divisor of \(a\) and \(b\text{.}\) There exist \(a^\prime, b^\prime \in \Z\) so that \(a = da^\prime\) and \(b = db^\prime\text{.}\) Hence

\begin{equation*} 1 = ax + by = (da^\prime)x + (db^\prime)y = d(a^\prime x + b^\prime y) \end{equation*}

implies \(d \mid 1\) and thus \(d = \pm 1\text{.}\) Since \(d\) was arbitrary, it follows that any common divisor of \(a\) and \(b\) must be either \(1\) or \(-1\text{.}\) Therefore the greatest common divisor of \(a\) and \(b\) is \(1\text{.}\)

🔗

Proposition A.10.

Assume \(a,b,c \in \Z\text{.}\) If the greatest common divisor of \(a\) and \(b\) is \(1\) and \(a\) divides \(bc\text{,}\) then \(a\) divides \(c\text{.}\)

🔗

Proof.

By assumption, there exist \(x,y \in \Z\) such that \(ax + by = 1\) and \(d \in \Z\) such that \(bc = ad\text{.}\) Multiply both sides by \(c\) to see

\begin{equation*} c = acx + bcy = acx + ady = a(cx + dy). \end{equation*}

Therefore \(a\) divides \(c\text{.}\)

🔗

Prev Top Next