Euclidean Algorithm (by Example)

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

The Euclidean Algorithm is an ancient method for finding the greatest common divisors (gcd) of two integers. The algorithm also generates the information necessary to write the gcd as a linear combination of the given integers. The Euclidean Algorithm is proven using previously established lemmas. Finally, emphasis is placed on its proof and examples of its use.

The Euclidean Algorithm is attributed to an ancient Greek mathematician named Euclid, who expressed it as the most effective method for establishing the greatest common divisor of a given set of two integers.

Indeed, the algorithm has extensive applications, both theoretically and practically. In number theory, for instance, the algorithm is used in expressing fractions into their simplest forms, and in executing division calculations in modular arithmetic. Also, the algorithm can be used in problems of Diophantine Equations, such as in solving problems related to the Chinese Remainder Theorem.

With that in mind, let us define what an Euclidean Algorithm is through the Lemma below.

An Important Lemma Needed

Here is the basic idea of the Euclidean Algorithm: divide $a$ by $b,$ obtaining the quotient $q_1$ and the remainder $r_1$. Then, if $r_1$ is not zero, divide $b$ by $r_1$ obtaining the quotient $q_2$ and remainder $r_2$. Then if $r_2$ is not zero then we repeat this process and divide $r_1$ by $r_2$, obtaining the quotient $q_3$ and remainder $r_3$. This process is repeated until we first obtain the remainder of zero. At the conclusion of the process we have the greatest common divisor which is the last nonzero remainder.

The next lemma is used in the proof of the Euclidean Algorithm.

Lemma. If $a$ and $b$ are positive integers. If $a=b q+r$ for some positive integers $q$ and $r$, then $(a,b)=(b,r)$.

For example, in the case that $288=40(7)+8$ we have $$ S = \{d\in \mathbb{Z} : d\mid 288, d\mid 40\} = \{\pm1, \pm 2, \pm 4\pm, \pm 8\} $$ and $$T=\{d\in \mathbb{Z} : d\mid 40, d\mid 8\} =\{\pm1, \pm 2, \pm 4\pm, \pm 8\}$$ Clearly, $S=T$ and both sets are finite.

Proof. Assume $a=bq+r$. Let $S$ and $T$ be the set of common divisors of $a$ and $b$ and of $b$ and $r$, respectively; that is, $$ S=\{d\in \mathbb{Z} : d\mid a \text{ and } d\mid b\}$$ $$T=\{d\in \mathbb{Z} : d\mid b \text{ and } d\mid r\}. $$ Let $d\in S$. So $d$ divides $a$ and $b$ and thus divides $b$ and $r=a-b q$. Hence $d\in T$.

To show the reverse inclusion $T\supseteq S$, if $d\in T$ then $d$ divides $b$ and $r$. Then $d$ divides $a=bq+r$ and $b$, and so $d\in S$.

We have shown $S\subseteq T$ and $T\subseteq S$; and therefore, $S=T$. Since these are finite sets the greatest common divisor of $a$ and $b$ is the same as the greatest common divisor of $b$ and $r$.

Finding the GCD is an Euclidean Algorithm Example

The process of finding the GCD between two numbers relies on the ability to write the numbers as products of their respective prime factors. In a similar fashion, the Euclidean Algorithm describes the iterative process of expressing a number as a product of its primes.

Example. Find $(345688, 245994)$.

Solution. By the Division Algorithm, \begin{align*} & 345688 =245994(1)+99694 \, \text{ with } \, 0\leq 99694 < 245994 \\ & 245994 =99694(2)+46606 \, \text{ with } \, 0\leq 46606 < 99694 \\ & 99694 =46606(2)+6482 \, \text{ with } \, 0\leq 6482 < 46606 \\ & 46606 =6482(7)+1232 \, \text{ with } \, 0\leq 1232 < 6482 \\ & 6482 =1232(5)+322 \, \text{ with } \, 0\leq 322 < 1232 \\ & 1232 =322(3)+266 \, \text{ with } \, 0\leq 266 < 322 \\ & 322 =266(1)+56 \, \text{ with } \, 0\leq 56 < 266 \\ & 266 =56(4)+42 \, \text{ with } \, 0\leq 42 < 56 \\ & 56 =42(1)+14 \, \text{ with } \, 0\leq 14 < 42 \\ & 42 =14(3)+0 \, \text{ with } \, 0\leq 0 < 14 \end{align*} Therefore, $(345688, 245994)=14$.

Example. Let $d=(328,288)$. Find $d$ and write it as a linear combination of 328 and 288.

Solution. By the Division Algorithm, \begin{align*} 328 & =288(1)+40 \, \text{ with } \, 0\leq 40<288 \\ 288 & =40(7)+8 \, \text{with} \, 0\leq 8<40 \\ 40 & =8(5)+0 \, \text{ with } \, 0\leq 8<40 \end{align*} Now, $d=(328,288)=8$ follows from $$(328,288)=(288,40)=(40,8)=(8,0)=8.$$ We can use the above computation to write $8$ as a line recombination of 328 and 288 using back substitution: \begin{align*} & 8=288-40(7) \\ & 8=288-328-288(1) \\ & 8= 8(288)-7(328) \end{align*}

About Euclid’s Algorithm

One way to view the Euclidean algorithm is as the repeated application of the Division Algorithm.

We can visualize the greatest common divisor. For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60.

Precisely, the greatest common divisor of two numbers $a$ and $b$ is the product of the prime factors shared by the two numbers, where a same prime factor can be used multiple times, but only as long as the product of these factors divides both $a$ and $b.$ For example, since 1386 can be factored into $2 \times 3 \times 3 \times 7 \times 11$, and 3213 can be factored into $3 \times 3 \times 3 \times 7 \times 17$, the greatest common divisor of 1386 and 3213 equals $63 = 3 \times 3 \times 7$, the product of their shared prime factors.

In particular, if two numbers have no prime factors in common, they are relatively prime. A important feature of the Euclidean algorithm is that it can find the gcd efficiently without having to compute the prime factors. Factorization of large integers is believed to be a computationally very difficult problem, and the security of many modern cryptography systems is based upon its infeasibility.

Consider the question of finding the greatest common divisor of two numbers. For example, let $a=288$ and $b=3266$, what is $(3266,288)$? We apply the Division Algorithm to obtain $$3266=11(288)+98 \text{ with } 0\leq 98 <288$$ and $(3266,288)=(288,98).$ Again, we apply the Division Algorithm to obtain $$ 288=2(98)+92 \text{ with } 0\leq 92 <98$$ and $(3266,288)$ $=(288,98)$ $=(98,92).$ Again, we apply the Division Algorithm to obtain $$98=1(92)+6 \text{ with } 0\leq 6 <92$$ and $(3266,288)$ $=(288,98)$ $=(98,92)$ $=(92,6)=2.$

The Euclidean Algorithm and its Proof

We now write this process in a general format and call it the Euclidean Algorithm.

Theorem. (Euclidean Algorithm) Let $a$ and $b$ be positive positive integers with $a\geq b$. If $b\nmid a$, then apply the division algorithm repeatedly as follows: $$ a=b q_0+r_0 \text{ with } 0\leq r_0.$$ This process ends after a finite number of steps; that is, for some $k$: $$ r_{k-2}=r_{k-1} q_k+r_k \text{ with } 0\leq r_k<r_{k-1} $$ where $r_{k-1}=r_k q_{k+1}+0 $ and $r_k=(a,b).$

Proof. The proof follows from the property: if $a=b q+r,$ then $(a,b)=(b,r).$ Thus, if $b|a,$ then $a=b q+0$ and so $(a,b)=(b,0)=b.$ Notice \begin{align*} (a,b) & =\left(b,r_0\right) \\ & =\left(r_0,r_1\right) \\ & =\cdots =\left(r_{k-2},r_{k-1}\right) \\ & =\left(r_{k-1},r_k\right) \\ & =\left(r_k,0\right) =r_k \end{align*} as desired.

In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers.

Euclidean Algorithm

Exercises on the Euclidean Algorithm

Exercise. Use the Euclidean Algorithm to find the following greatest common divisors.

$(1) \quad (221,187)$

$(2) \quad (51,87)$

$(3) \quad (105,300)$

$(4) \quad (34709,100313)$

$(5) \quad (64,38,190)$

$(6) \quad (15,35,90)$

$(7) \quad (100,210,540)$

$(8) \quad (300,2160,5040)$

$(9) \quad (240, 660, 5540, 9980)$

$(10) \quad (1240, 6660, 15540, 19980)$

Exercise. Find $(143,227),$ $(306,657),$ and $(272,1479).$

Exercise. Use the Euclidean Algorithm to find integers $x$ and $y$ satisfying the following.

$(1) \quad (56,72)=56x+72y$

$(2) \quad (24,138)=24x+138y$

$(3) \quad (119,272)=119x+272y$

$(4) \quad (1769,2378)=1769x+2378y$

Exercise. Find integers $x$ and $y$ satisfying $$ (198,288,512) = 198x+288y+512z. $$

Exercise. Find $\gcd (143,227),$ $\gcd (306,657),$ and $\gcd (272,1479).$

Exercise. Show that if $k>0$ then $\gcd (k a,k b)=k \gcd (a,b).$

Exercise. Show that if $r|a$, $r|b$, and $r|c$, then $r|\gcd(a,b,c)$.

Exercise. Prove that, if $a_1, a_2,\ldots a_m$ are pairwise relatively prime, then $$(a_1,a_2,\ldots, a_n)=1.$$

Exercise. Use the Euclidean algorithm to find $(1372,490)$ and write the GCD as a linear combination of 1372 and 490.

Exercise. Use the Euclidean algorithm to find $d=(500,50,40)$ and write $d$ as a linear combination of the three given integers.

Exercise. Use the Euclidean Algorithm to find $(28,48,24)$.

Exercise. Use the Euclidean Algorithm to find $(28,48,24)$.

Exercise. Use the Euclidean Algorithm to find $(34709,100313).$

Exercise. Use the Euclidean Algorithm to find the greatest common divisor $(105,300)$ and then write this as a linear combination of these integers.

Exercise. Use the Euclidean Algorithm to find the multiplicative inverse for 91 modulo 191.

Leave a Comment