1.7: The Euclidean Algorithm

Unlike the Division Algorithm, the Euclidean Algorithm really is an algorithm. It provides a method to compute \(\gcd(a,b)\). Since as already noted \(\gcd(0,0)=0\), \(\gcd(a,b)=\gcd(|a|,|b|)\), and \(\gcd(a,b) = \gcd(b,a)\), it suffices to give a method to compute \(\gcd(a,b)\) when \(a\ge b\ge 0\).

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 6.2 the largest divisor of \(a\) is \(|a|\). Since \(a>0\), \(|a|=a\). This shows that \(\gcd(a,0)=a\).

Remark \(\PageIndex{1}\)

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

Exercise \(\PageIndex{1}\)

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

Now having done Exercise \(\PageIndex{1}\) we only need to consider the case \(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 3.1(3) \(d\mid r\). Thus \(d\mid b\) and \(d\mid r\). Next assume \(d\mid b\) and \(d\mid r\). Using Theorem 3.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{2}\)

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 I will give an example to show how it goes.

Example \(\PageIndex{1}\)

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

\[\begin{aligned} \gcd(803,154) &=\gcd(154,33) \quad \mbox{ since } 803 =154\cdot5+33 \\ \gcd(154,33) &=\gcd(33,22) \quad \mbox{ since } 154 =33\cdot4+22 \\ \gcd(33,22) &=\gcd(22,11)\quad \mbox{ since } 33 =22\cdot1+11 \\ \gcd(22,11) &=\gcd(11,0) \quad \mbox{ since } 22 =11\cdot2+0 \\ \gcd(11,0) &= 11. \end{aligned}\] Hence \(\gcd(803,154)=11\).

Remark \(\PageIndex{3}\)

Note that 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.

Exercise \(\PageIndex{2}\)

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

Remark \(\PageIndex{4}\)

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\)