7.3: Euclidean Algorithm

How do we find \(\operatorname{gcd}(a, b)\), for \(a, b \in \mathbb{N}\) ? One might invoke the Fundamental Theorem of Arithmetic and compare the prime decompositions of \(a\) and \(b\). Suppose \[a=\prod_{n=1}^{N} p_{n}^{r_{n}}\] and \[b=\prod_{n=1}^{N} p_{n}^{s_{n}}\] where \(r_{n}, s_{n} \in \mathbb{N}\) for \(1 \leq n \leq N\). If \(t_{n}=\min \left(r_{n}, s_{n}\right)\) for \(1 \leq n \leq N\), then \[\operatorname{gcd}(a, b)=\prod_{n=1}^{N} p_{n}^{t_{n}}\] However finding the prime decomposition of an integer can be quite difficult. We shall define an operation on pairs of integers that after a reasonable number of applications will yield the greatest common divisor of the integers.

If \(a, b \in \mathbb{N}, a>b>0\), define \(E: \mathbb{N}^{2} \rightarrow \mathbb{N}^{2}\) by \[E(a, b)=(b, r)\] where \(r\) is the unique remainder (when dividing \(a\) by \(b\) ) whose existence was proved in the Division Algorithm. That is, if \[a=q b+r\] with \(0 \leq r<b\), then define \[E(a, b):=(b, r) .\] If \(b=0\), then let \[E(a, 0)=(a, 0) .\] Let \((a, b) \in \mathbb{N}^{2}, a>b>0\). We define a sequence of elements in \(\mathbb{N}^{2}\), \(\left\langle E_{i}(a, b) \mid i \in \mathbb{N}\right\rangle\), by recursion: \[E_{0}(a, b)=(a, b)\] and if \(n>0\) \[E_{n}(a, b)=E\left(E_{n-1}(a, b)\right) .\] So long as \(E_{n}(a, b)\) has non-zero components, the sequence of second components is strictly decreasing, so it is clear that the sequence must eventually become fixed on an ordered pair (see Exercise 4.11). By the Division Algorithm, this will occur when the second component equals 0 . Let \(k\) be the smallest integer such that \[E_{k}(a, b)=E_{k+1}(a, b) .\] Then we say that \(\left\langle E_{n}(a, b) \mid n \in \mathbb{N}\right\rangle\) stabilizes at step \(k\). For \(n \geq k\), \[E_{n}(a, b)=E_{n+1}(a, b)=E_{k}(a, b) .\] If \(\left\langle E_{n}(a, b)\right\rangle\) stabilizes at step \(k\), it is obvious that \(k \leq b\). Typically, the sequence stabilizes much faster than this. THEOREM 7.12. Let \(a, b \in \mathbb{N}, a>b>0\). The non-zero component on which the sequence \[\left\langle E_{n}(a, b) \mid n \in \mathbb{N}\right\rangle\] stabilizes is \(\operatorname{gcd}(a, b)\).

Proof. Let \(a\) be fixed, we argue by induction on the smaller of the integers, \(b\).

Base case: \(b=1\)

Then for any \(a>1\), \[E(a, 1)=(1,0)\] and the sequence \(\left\langle E_{n}(a, 1)\right\rangle\) stabilizes at step 1 with non-zero component \(1 .\)

Induction step:

Let \(b>1\). Assume the result holds for all \(c<b\) - that is, for any \((a, c) \in \mathbb{R}^{2}\), where \(c<b<a\), the non-zero component of the ordered pair at which the sequence \(\left\langle E_{n}(a, c)\right\rangle\) stabilizes is \(\operatorname{gcd}(a, c)\). We show that the non-zero component of the ordered pair at which the sequence \(\left\langle E_{n}(a, b)\right\rangle\) stabilizes is \(\operatorname{gcd}(a, b)\). If \(a>b>0\) then \[E(a, b)=(b, a-q b)\] where \(0 \leq a-q b<b\). By the induction hypothesis, the non-zero component of the ordered pair at which the sequence \(\left\langle E_{n}(b, a-q b)\right|\) \(n \in \mathbb{N}\rangle\) stabilizes is \(\operatorname{gcd}(b, a-q b)\). By Proposition \(7.9\) \[\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a-q b) .\] So the non-zero component of the ordered pair at which the sequence \[\left\langle E_{n}(a, b) \mid n \in \mathbb{N}\right\rangle\] stabilizes is \(\operatorname{gcd}(a, b)\). By the induction principle, the result holds for all ordered pairs \((a, b) \in \mathbb{N}^{2}\) where \(a>b>0\).

An algorithm is a set of executable computational instructions. The Euclidean algorithm is the following set of instructions:

Given a pair of natural numbers, \(a>b>0\), compute the sequence \(\left\langle E_{n}(a, b) \mid n \in \mathbb{N}\right\rangle\) until the sequence stabilizes. The non-zero component of the ordered pair on which the sequence stabilizes is \(\operatorname{gcd}(a, b)\).

EXAMPLE 7.13. Let \(a=29712375\) and \(b=119119\). Find the \(\operatorname{gcd}(a, b)\). We use the Euclidean Algorithm. So \[\begin{gathered} E_{0}(a, b)=(a, b) \\ E_{1}(a, b)=E(a, b)=(b, 51744) \\ E_{2}(a, b)=E(b, 51744)=(51744,4851) \\ E_{3}(a, b)=E(51744,4851)=(4851,1078) \\ E_{4}(a, b)=E(4851,1078)=(1078,539) \\ E_{5}(a, b)=E(1078,539)=(539,0) . \end{gathered}\] Therefore \(\operatorname{gcd}(a, b)=539\). If you employ the Fundamental Theorem of Arithmetic, with some work you can determine that \[29,712,375=\left(3^{2}\right)\left(5^{3}\right)\left(7^{4}\right)(11)\] and \[119,119=\left(7^{2}\right)(11)(13)(17) .\] So \(\operatorname{gcd}(a, b)=\left(7^{2}\right)(11)=539\).