Euclidean Algorithm

Section 2.2 Euclidean Algorithm

Definition 2.2.1.

The least common multiple of \(a,b\in\mathbb{Z}\) is the number \(l\gt 0\) such that

\(a\vert l\) and \(b\vert l\)
if \(a\vert c\) and \(b\vert c,\) then \(l\leq c.\)

Example 2.2.2.

If \(a=25\) and \(b=10,\) then \(\gcd(25,10)=5\) and \(\mathrm{lcm}(25,10)=50.\) As we expect we also see that

\begin{equation*} \gcd(25,10)\cdot \mathrm{lcm}(25,10)=5\cdot 50=250=25\cdot 10. \end{equation*}

Theorem 2.2.3.

For \(a,b\in\mathbb{N}, \gcd(a,b)\vert \mathrm{lcm}(a,b).\)

Theorem 2.2.4.

Let \(a,b\in\mathbb{N}.\) Then \(\mathrm{lcm}(a,b)\cdot \gcd(a,b)=ab.\)

What if we actually want to find the \(\gcd(a,b)?\) First a lemma.

Lemma 2.2.5.

If \(a=qb+r,\) then \(\gcd(a,b)=\gcd(b,r).\)

If \(d=\gcd(a,b),\) then since \(d\vert a\) and \(d\vert b,\) we have \(d\vert (a-qb),\) or rather, \(d\vert r.\) Thus, \(d\) is a common divisor of \(b\) and \(r,\) hence \(d\leq \gcd(b,r).\) Now since \(c:=\gcd(b,r)\) is a common divisor of \(b\) and \(r,\) then \(c\vert (qb + r),\) so that \(c\vert a.\) This makes \(c\) a common divisor of \(a\) and \(b,\) so \(c\leq d.\) Thus \(d=\gcd(b,r).\)

Theorem 2.2.6 (Euclidean Algorithm).

Let \(a,b\in\mathbb{N}\) with \(b\lt a.\) Then there exist \(q_1, q_2, q_3,..., q_n, q_{n+1}\in\mathbb{Z}\) and \(r_1, r_2, r_3,..., r_n\in\mathbb{N}\) satisfying \(0\lt r_n\lt r_{n-1}\lt ...\lt r_2\lt r_1\lt b\) and

\begin{align*} a \amp =bq_1+r_1\\ b \amp =r_1q_2+r_2\\ \amp \vdots\\ r_{n-2} \amp =r_{n-1}q_{n}+r_n\\ r_{n-1} \amp =r_{n}q_{n+1}. \end{align*}

Furthermore, \(r_n=\gcd(a,b).\)

Proof.

All existence statements follow from the Division Algorithm and the Well Ordering Principle. From the last equation we have that \(r_n\vert r_{n-1}.\) From the second to last equation we have that \(r_n\vert r_{n-2},\) and so on until we eventually have \(r_n\vert a\) and \(r_n\vert b.\) Thus \(r_n\) is a common divisor of \(a\) and \(b,\) and also \(r_n \geq 1.\)

Now let \(c\in\mathbb{Z}\) with \(c\vert a\) and \(c\vert b.\) Reversing the argument of the preceding paragraph gives from the first equation \(c\vert r_1.\) From the second equation we have \(c\vert r_2,\) and so on and so forth until we have \(c\vert r_n,\) so that we have that \(r_n=\gcd(a,b).\)

Example 2.2.7.

What is the \(\gcd(1492,1066)?\)

Solution.

To find this we use the Euclidean Algorithm. We write

\begin{align*} 1492 \amp = 1\cdot 1066 + 426\\ 1066 \amp = 2\cdot 426 + 214\\ 426 \amp = 1\cdot 214 + 212\\ 214 \amp = 1\cdot 212 + 2\\ 212 \amp= 2\cdot 106 + 0. \end{align*}

Thus \(\gcd(1492,1066)=2.\)

As previously demonstrated, the \(\gcd(a,b)\) can be written as a linear combination of \(a,b\) with some integers \(x,y;\) that is,

\begin{equation*} \gcd(a,b)=ax+by. \end{equation*}

But how do we find \(x\) and \(y?\)

For this we use the Euclidean Algorithm as well, just backwards. Starting with the next to last equation write

\begin{equation*} r_n=r_{n-2}-q_nr_{n-1}. \end{equation*}

Now solve the preceding equation in the algorithm for \(r_{n-1}\) and substitute to obtain

\begin{align*} r_n \amp =r_{n-2}-q_n(r_{n-3}-q_{n-1}r_{n-2})\\ \amp =(1+q_nq_{n-1})r_{n-2}+(-q_n)r_{n-3}, \end{align*}

and so we have \(r_n\) as a linear combination of \(r_{n-2}\) and \(r_{n-3}.\) Continuing backwards we keep eliminating remainders until we reach are left with \(r_n=\gcd(a,b)\) as a linear combination of \(a\) and \(b.\)

Example 2.2.8.

In the example above \(d=\gcd(1492,1066)=2.\) To write this as a linear combination, we have

\begin{align*} d \amp = 2\\ \amp = 214-1\cdot 212\\ \amp = 214-1\cdot (426-1\cdot 214)\\ \amp = -1\cdot 426+2\cdot 214\\ \amp = -1\cdot 426+2\cdot (1066-2\cdot 426)\\ \amp = 2\cdot 1066-5\cdot 426\\ \amp = 2\cdot 1066-5\cdot (1492-1\cdot 1066)\\ \amp = -5\cdot 1492+7\cdot 1066. \end{align*}