1.8: The Euclidean Algorithm

The Euclidean Algorithm is named after Euclid of Alexandria, who lived about 300 BCE. The algorithm\(^{1}\) described in this chapter was recorded and proved to be successful in Euclid’s Elements, so this algorithm is over two thousand years old. It provides a simple method to compute \(\gcd(a,b)\), even if we do not know much about the divisors of \(a\) and \(b\).

Since, as already noted, \(\gcd(0,0)=0\) and \(\gcd(a,b)=\gcd(|a|,|b|)\) and \(\gcd(a,b) = \gcd(b,a)\), in order to compute \(\gcd(a,b)\) it is enough to find a method for computing \(\gcd(a,b)\) when \(a\ge b\ge 0\), so we will assume that \(a\) and \(b\) satisfy these inequalities.

Before discussing the Euclidean Algorithm, we establish a few useful facts. First of all, as Exercise \(\PageIndex{1}\) establishes, if \(a>0\), then \(\gcd(a,a)=a\). The next result is in a similar vein.

Lemma \(\PageIndex{1}\)

If \(a>0\), then \(\gcd(a,0)=a\).

Proof

Since every integer divides \(0\), \(C(a,0)\) is just the set of divisors of \(a\). By Lemma 1.7.2 the largest divisor of \(a\) is \(|a|\). Since \(a>0\), \(|a|=a\). This shows that \(\gcd(a,0)=a\).

With these facts we are now reduced to the problem of finding \(\gcd(a,b)\) when \(a>b>0\).

Lemma \(\PageIndex{2}\)

Let \(a>b>0\). If \(a=bq+r\), then \[\gcd(a,b)=\gcd(b,r).\nonumber \]

Proof

It suffices to show that \(C(a,b)=C(b,r)\), that is, the common divisors of \(a\) and \(b\) are the same as the common divisors of \(b\) and \(r\). To show this first let \(d\mid a\) and \(d\mid b\). Note that \(r=a-bq\), which is a linear combination of \(a\) and \(b\). So by Theorem 1.4.1(3) \(d\mid r\). Thus \(d\mid b\) and \(d\mid r\). Next assume \(d\mid b\) and \(d\mid r\). Using Theorem 1.4.1(3) again and the fact that \(a=bq+r\) is a linear combination of \(b\) and \(r\), we have \(d\mid a\). So \(d\mid a\) and \(d\mid b\). We have thus shown that \(C(a,b)=C(b,r)\). So \(\gcd(a,b)=\gcd(b,r)\).

Remark \(\PageIndex{1}\)

The Euclidean Algorithm is the process of using Lemmas \(\PageIndex{2}\) and \(\PageIndex{1}\) to compute \(\gcd(a,b)\) when \(a>b>0\).

Rather than give a precise statement of the algorithm we will start with an example to show how it goes.

Example \(\PageIndex{1}\)

Let’s compute \(\gcd(803,154)\).

\(\gcd(803,154)\)	\(=\)	\(\gcd(154,33)\)	since \(803 =154\cdot5+33\);
\(\gcd(154,33)\)	\(=\)	\(\gcd(33,22)\)	since \(154 =33\cdot4+22\);
\(\gcd(33,22)\)	\(=\)	\(\gcd(22,11)\)	since \(33 =22\cdot1+11\);
\(\gcd(22,11)\)	\(=\)	\(\gcd(11,0)\)	since \(22 =11\cdot2+0\);
\(\gcd(11,0)\)	\(=\)	\(11\).

Hence \(\gcd(803,154)=11\).

By way of commentary, observe that in our repeated application of the Division Algorithm, both the dividend and divisor change at each step, with some numbers (like 33 and 22 above) appearing first as a remainder, then moving to be the divisor in the next division statement, and then finally serving as the dividend in the statement after that. Note that the process ends once a remainder of \(0\) is reached (this must happen, since at each step the remainders decrease). We always arrive at \(\gcd(a,b)\) as the last nonzero remainder.

Remark \(\PageIndex{2}\)

Note that in our example we have formed the \(\gcd\) of \(803\) and \(154\) without factoring \(803\) and \(154\). This method is generally much faster than factoring and can find \(\gcd\)’s when factoring is not feasible.

Exercises

Exercise \(\PageIndex{1}\)

Prove that if \(a>0\) then \(\gcd(a,a)=a\).

Exercise \(\PageIndex{2}\)

Let \(a>b>0\). Show that \(\gcd(a,b)=\gcd(b, a \bmod b)\).

(Hint: compare this statement to Lemma \(\PageIndex{2}\).)

Remark \(\PageIndex{3}\)

So if your calculator can compute \(a\bmod b\) you may use it when executing the Euclidean Algorithm.

Exercise \(\PageIndex{3}\)

Find \(\gcd(a,b)\) using the Euclidean Algorithm for each of the values below:

1. \(a=37\), \(b=60\)
2. \(a=793\), \(b=3172\)
3. \(a=25174\), \(b=42722\)
4. \(a=377\), \(b=233\)

Exercise \(\PageIndex{4}\)

Use the Euclidean Algorithm to show that if \(n\) is an odd integer, then each fraction of the form \[\frac{2n+2}{3n+2},\nonumber\] like \(\frac{4}{5}\) and \(\frac{8}{11}\), is already in lowest terms. (Hint: What is the greatest common divisor of the numerator and denominator?)\(^{2}\)

Exercise \(\PageIndex{5}\)

Write a paragraph describing the similarities and differences of the Euclidean Algorithm and the algorithm for converting a number into its base \(b\) representation.

Following are two small projects you may enjoy:

Exercise \(\PageIndex{6}\)

1. Carry out the Euclidean Algorithm to find \(\gcd(a,b)\) when \(a=13\) (always) and \(b\) is each number in the set \(\{1,2,\dots,12\}\) in turn. For which \(b\)’s does the Euclidean Algorithm take the most steps to produce \(\gcd(13,b)\)?
2. The numbers that led to longer procedures in the last part have something in common. If you’re not yet familiar with them, do an internet search to learn about “Fibonacci numbers.” How are Fibonacci numbers connected to what you observed in Part 1 of this exercise?
3. Do you have a prediction for which \(b\)’s will lead to the longest Euclidean Algorithm procedures if we compute \(\gcd(21,b)\)? Test it out!
4. Now do an internet search for webpages containing both the phrases “Euclidean algorithm" and “Fibonacci numbers". What do you find out?

Exercise \(\PageIndex{7}\)

Here is a simple game: Starting with distinct positive integers \(a\) and \(b\) on a sheet of paper, two players take turns trying to write a new number on the sheet, subject to the conditions that (1) the number does not already appear on the paper, and (2) the number is a positive number that is the difference of two numbers already on the paper.

For example, if the starting numbers were \(21\) and \(6\), the first player could add “\(15\)” to the paper, because \(21-6 = 15\). The second player could then write “\(9\)” (which equals \(15-6\)), and the first player could next write “\(12\)” (which is \(21-9\)) or “\(3\)” (which is \(9-6\)), and the game would continue.

The game ends when a player cannot find another number to add to the sheet of paper; that player loses the game. Answer the following questions.

1. If the game described above continued, who would win the game? Does it matter what choices are made by the players on their turns?
2. When the game above ends, which numbers are listed on the sheet of paper? What patterns do you see in this collection of numbers?
3. If the same game is played starting with any two distinct positive integers \(a\) and \(b\), the smallest integer on the paper at the end of the game has a special relationship to \(a\) and \(b\). What is this relationship, and why does it happen?
   (Hint: think of the results of this chapter!)
4. Can you devise a strategy of deciding which player to be (the first or the second player) if you wanted to be certain of winning the game, if you knew what \(a\) and \(b\) were? What would it be? Why would it work?

Footnotes

[1] Unlike the Division Algorithm, the Euclidean Algorithm really is an algorithm!

[2] This problem is adapted from a 2017 monthly contest of the Berkeley Math Circle. Accessed at https://mathcircle.berkeley.edu/site...files/handouts mc/problems/2017/mc4.pdf on August 17, 2021.