3. Extended Euclidean Algorithm

We have seen what the greatest common divisor is and one of its uses, namely it allows us observe under what conditions linear equations are soluble in the integers. In this post we will see one way to compute the greatest common divsior, the Extended Euclidean Algorithm. Before we get to the Extended Euclidean Algorithm we will start with the standard Euclidean Algorithm. It is named after Euclid a greek mathematician who is often called the “father of geometry” who described this algorithm as early as 300 BC. The essence of the Euclidean Algorithm is to apply Theorem 2.1 over and over until we get a remainder of zero, then we can extract the greatest common divisor.

Notation: $x \nmid y$ means x does not divide y.

Definition 3.1: Linear Combination

A linear combination of integers $x,y \in \mathbb{Z}$ is any expression of the form $ax+by$ where a and b are constants. (for our purposes a and b will always be integers).

This next theorem may look intimidating but once we go through an example and put numbers to the letters it will become clearer.

Theorem 3.1: (The Euclidean Algorithm) Let $a,b\in \mathbb{N}$ with $a\geq b>0$ and $b \nmid a$ . Let $r_{0}=0,r_{1}=b$ and apply Theorem 2.1 repeatedly to obtain a sequence of remainders $r_{2},r_{3},...,r_{n},r_{n+1}$ defined as follows:

$r_{0}=r_{1}q_{1} + r_{2}$ where $0<r_{2}<r_{1}$

$r_{1} =r_{2}q_{2}+r_{3}$ where $0<r_{3}<r_{2}$

…

$r_{n-2}=r_{n-1}q_{n-1}+r_{n}$ where $0<r_{n}<r_{n-1}$

$r_{n-1}=r_{n}q_{n}+r_{n+1}$ where $r_{n+1}=0$

Then $gcd(a,b)=r_{n}$

Proof:

Consider the sequence of remainders, the $r_{i}$ are strictly decreasing non-negative integers and so at some stage $r_{n+1}=0$ . We have that for any $x,y,z\in \mathbb{Z}$ we have gcd(x,y)=gcd(x+zy,y). So in terms of our remainders this is $gcd(r_{i},r_{i+1})=gcd(r_{i+1}q_{i+1}+r_{i+2},r_{i+1})=gcd(r_{i+2},r_{i+1})=gcd(r_{i+1}),gcd(r_{i+2})$ . Applying this over and over yields; $gcd(a,b)=gcd(r_{0},r_{1})=gcd(r_{1},r_{2})=gcd(r_{2},r_{3})=...=gcd(r_{n-1},r_{n})=r_{n}.$ where the last equality is because $r_{n}|r_{n-1}$ .

QED

Remember Bezout’s Identity from the last post? well we can find $x,y \in \mathbb{Z}$ such that $gcd(a,b)=ax+by$ (i.e. we can express the gcd of a and b as a linear combination of a and b) by ‘working backwards’. We can do this because each remainder can be expressed as a linear combination of the two previous remainders, so can the remainders before those and eventually it can be expressed in terms of a and b as we will see in the following example;

Example 3.1: Calculate the Greatest Common divisor of 720 and 333 and express it as a linear combination of 720 and 333.

$720 = 333 \times 2 + 54$

$333=54 \times 6 +9$

$54 = 9 \times 6 + 0$

therefore gcd(720,333)=9. (Try and compare this example to the previous theorem and see where the numbers fit the $r_{i}'s$ ). Now lets work backwards to express 9 as a linear combination of 720 and 333.

$9 =333 \times 1 - 54 \times 6$

$54 = 720 \times 1 - 333 \times 2$ and so $9 = 333 \times 1 - (720 \times 1 -333 \times 2) \times 6$

collecting like terms yields $9= 720 \times (-6) +333 \times 13$ .

So we have now seen how and why the Euclidean Algorithm works, now for the Extended Euclidean Algorithm. The Extended Euclidean Algorithm essentially combines the ‘working backwards’ step we did in the previous example while we compute the gcd, and so it computes the gcd as a linear combination of the two integers.

The sequences of quotients, $q_{i}$ , and remainders, $r_{i}$ , defined in the Euclidean Algorithm, we now define the sequence of integers $x_{i}, y_{i}$ , such that $r_{i} = ax_{i} + by_{i}$ . Remember that we define $r_{n}$ to be the last non zero remainder and that $r_{n}=gcd(a,b)$ . Therefore we have $gcd(a,b)=r_{n}=ax_{n}+by_{n}$ and so we set $(x,y)=(x_{n},y_{n}$ . Let us now explicitly define $x_{i}$ and $y_{i}$ . So from Theorem 3.1 $r_{0}=a$ and $r_{1}=b$ and so clearly $r_{0}=a\times 1 +b\times 0$ and $r_{1}=a\times 0 +b\times 1$ and so we set $(x_{0},y_{0}):= (1,0)$ and $(x_{1},y_{1}):=(0,1)$ . Now for $i\geq 2$ we recursively define by

$(x_{i},y_{i}):=(x_{i-2},y_{i-2})-q_{i-1}(x_{i-1},y_{i-1})$

which will become clear with an example.

Example 3.2: Let calculate gcd(720,333) again but this time using the Extended Euclidean Algorithm;

and so $gcd(720,333)=9=720\times (-6) + 333\times 13$

r_{i-2} — and so $gcd(720,333)=9=720\times (-6) + 333\times 13$

Compare this with example 3.1 to help you understand where everything is coming from. A useful exercise is to compute the gcd of any two integers and then check your answer at this website https://planetcalc.com/3298/ .

3. Extended Euclidean Algorithm

Published by Mathsnotes

Leave a comment Cancel reply

Share this:

Related

Published by Mathsnotes

Leave a comment Cancel reply