Extended Euclidean Algorithm | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll explain the extended Euclidean algorithm (EEA). It’s a tool widely used in cryptography and one of the fundamental algorithms in number theory. In addition to its recursive version, we’ll present its iterative variant.

2. Bézout’s Identity

Bézout’s identity states that the greatest common divisor (GCD) of any two integers is their linear combination. So, if $d$ is the GCD of $a$ and $b$ , then there exist integers $x$ and $y$ such that:

(1) $\begin{equation*} d = xa + yb \end{equation*}$

For example, if $a=5$ and $b=3$ , then $d=GCD(5,3)=1$ and:

$1 = -1\cdot 5 + 2\cdot 3$

The extended Euclidean algorithm (EEA) finds $\boldsymbol{x}$ and $\boldsymbol{y}$ , which are called Bézout’s coefficients of $\boldsymbol{a}$ and $\boldsymbol{b}$ . As we’ll see, EEA is a modification of the Euclidean algorithm for finding the GCD of two numbers.

2.1. Assumptions

In what follows, we’ll assume that $a$ and $b$ are both positive and that $a > b$ . We lose no generality under those assumptions because:

$\begin{aligned} GCD(a, b) &=&& GCD(|a|, |b|) \\ GCD(a, b) &=&& GCD(b, a) \\ GCD(a, 0) &=&& a \end{aligned}$

which means that we can consider only the case $\boldsymbol{a \geq b > 0}$ :

If either of $a$ and $b$ is zero, then we output the other number as their GCD and set the corresponding coefficients to $1$ and $0$ .
If $a$ (or $b$ ) is negative, then we replace it with its absolute value.
Finally, we can switch $a$ and $b$ if $a<b$ .

3. The Euclidean Algorithm (EA)

The Euclidean algorithm (EA) finds the GCD of $a$ and $b$ by using the fact that:

$GCD(a, b) = GCD(b, a\bmod b)$

and applying Euclidean division until it gets zero as the remainder:

$\begin{aligned} \underbrace{a}_{a_1} &=&& \underbrace{\left\lfloor\frac a b \right\rfloor}_{q_1}\cdot \underbrace{b}_{a_2} + \underbrace{(a \bmod b)}_{a_3} &&(1\leq a_3 < b)\\ a_2 &=&& q_2\ a_3 + a_4 &&(1 \leq a_4 < a_3)\\ \vdots \\ a_{n-3} &=&& q_{n-3} a_{n-2} +a_{n-1} && (1 \leq a_{n-1} < a_{n-2}) \\ a_{n-2} &=&& q_{n-2} a_{n-1} +a_{n} && (1 \leq a_{n} < a_{n-1}) \\ a_{n-1} &=&& q_{n-1} a_{n} +a_{n+1} && (1 \leq a_{n+1} < a_n) \\ a_{n} &=&& q_{n}a_{n+1} + 0 &&(a_{n+2}=0) \end{aligned}$

The last nonzero remainder ( $\boldsymbol{a_{n+1}}$ ) is the GCD of $\boldsymbol{a}$ and $\boldsymbol{b}$ . As we see, the recursion is:

(2) $\begin{equation*} \begin{cases} a_1 = a\\ a_2 = b \\ a_k = q_k a_{k+1} + a_{k+2},& k>2 \end{cases} \end{equation*}$

where $q_k = \left\lfloor \frac{a_{k}}{a_{k+1}} \right \rfloor$ . We’ll find it useful to re-formulate the recursive rule so that we express the remainder in terms of the dividend and the divisor:

(3) $\begin{equation*} \begin{cases} a_1 = a\\ a_2 = b \\ a_{k+2} =a_k - q_k a_{k+1}, & k>2 \end{cases} \end{equation*}$

4. The Recursive Version of the Extended Euclidean Algorithm

The recursive extension of EA (REEA) runs just like the regular EA until it computes $a_{n+1}$ , the GCD of the input numbers $a$ and $b$ . At that point, it starts recursing back to the beginning, revisiting the division steps of $a_{n-1}, a_{n}, \ldots, a_2, a_1$ backward. After backtracking to a division step, REEA expresses the GCD as a combination of the step’s divisor and dividend.

So, from the second-to-last division, we get:

$a_{n+1} = a_{n-1} -q_{n-1}a_{n} \\$

Now, backtracking to $a_{n-2} = q_{n-2} a_{n-1} +a_{n}$ , we replace $a_{n}$ with $a_{n-2}-q_{n-2} a_{n-1}$ , so we have:

$\begin{aligned} a_{n+1} &=&& a_{n-1} - q_{n-1}(a_{n-2}-q_{n-2}a_{n-1}) \\ &=&& (1+q_{n-1}q_{n-2})a_{n-1} +(- q_{n-1})a_{n-2} \end{aligned}$

In general, let’s say we revisited the division step $a_{k+1} = q_{k+1} a_{k+2}+a_{k+3}$ and expressed $a_{n+2}$ as a linear combination of $a_{k+1}$ and $a_{k+2}$ :

(4) $\begin{equation*} a_{n+2} = x_{k+1} a_{k+1} + y_{k+1}a_{k+2} \end{equation*}$

Recursing one step back, we substitute $a_{k+2}$ with $a_k - q_k a_{k+1}$ in Equation (4):

(5) $\begin{equation*} \begin{aligned} a_{n+2} &=&& x_{k+1} a_{k+1} + y_{k+1}(a_k - q_k a_{k+1}) \\ & =&& \underbrace{y_{k+1}}_{x_k}a_k+ \underbrace{(x_{k+1}-y_{k+1} q_k)}_{y_k}a_{k+1} \end{aligned} \end{equation*}$

Therefore, we obtain the following backward recursive rules:

(6) $\begin{equation*} \begin{cases} x_{n-1} = 1 \\ y_{n-1} = -q_{n-1} \\ x_k=y_{k+1}, & 1 \leq k < n - 1 \\ y_k = x_{k+1}-y_{k+1} q_k, & 1 \leq k < n - 1 \end{cases} \end{equation*}$

We apply them going backward through the division steps until we finally represent the GCD as a linear combination of $\boldsymbol{a_1=a}$ and $\boldsymbol{a_2=b}$ :

4.1. Example

Let’s say that $a=234$ and $b=44$ . Applying the algorithm, we do five Euclidean divisions:

$\begin{aligned} 254 &= 5\cdot 44 + 34 \\ 44 &= 1\cdot 34 + 10 \\ 34 &= 3\cdot 10 + 4 \\ 10 &= 2\cdot 4 + \boldsymbol{2}\\ 4 &= 2\cdot 2 + 0 \end{aligned}$

Or, using recurrence (3):

$\begin{aligned} 34 &= 254 - 5\cdot 44 \\ 10 &= 44 - 1 \cdot 34 \\ 4 &= 34 - 3 \cdot 10 \\ \boldsymbol{2} & = 10 - 2\cdot 4 \\ 0 &= 4 - 2\cdot 2 \end{aligned}$

After identifying the GCD, we go backward one division step. From there, we get $2 = 1\cdot 10 + (-2)\cdot 4$ and climb one step up to see what to substitute $4$ with:

After some elementary algebra, we get that $2 = (-2)\cdot 34 + 7 \cdot 10$ . Then, we go up a step again to see what to replace $10$ with:

and get $2 = 7 \cdot 44 + (-9)\cdot 34$ . In the end, we backtrack to the first division step:

and obtain Bézout’s coefficients:

(7) $\begin{equation*} GCD(254, 44) = 2 = (-9)\cdot 254 + 52 \cdot 44 \end{equation*}$

5. The Iterative Version of the Extended Euclidean Algorithm

We can compute the coefficients without backtracking. The idea is to express each step’s remainder as a linear combination of $\boldsymbol{a_1=a}$ and $\boldsymbol{a_2=b}$ . To do so, we start by noting that:

$\begin{aligned} a_1 &=&& \underbrace{1}_{x_1}\cdot a_1 + \underbrace{0}_{y_1} \cdot a_2 \\ a_2 &=&& \underbrace{0}_{x_2}\cdot a_1 + \underbrace{1}_{y_2} \cdot a_2 \end{aligned}$

In general, we’ll have:

(8) $\begin{equation*} a_{k} = x_ka_1+y_ka_2 \end{equation*}$

and we want rules for calculating the coefficients in a step given those from the previous steps. As it turns out, we need only the coefficients from the previous two steps. So, let’s suppose that we know $x_{k}$ , $x_{k+1}$ , $y_{k}$ , and $y_{k+1}$ for some $k \geq 1$ :

$\begin{aligned} a_{k} &=&& x_ka_1+y_ka_2 \\ a_{k+1} &=&& x_{k+1}a_1+y_{k+1}a_2 \end{aligned}$

Using Equation (3), we get:

(9) $\begin{equation*} \begin{aligned} a_{k+2} &=&& a_{k} - q_k a_{k+1} \\ &=&& (x_ka_1+y_ka_2)-q_k(x_{k+1}a_1+y_{k+1}a_2) \\ &=&& \underbrace{(x_k-q_kx_{k+1})}_{x_{k+2}}a_1 + \underbrace{(y_k-q_ky_{k+1})}_{y_{k+2}}a_2 \end{aligned} \end{equation*}$

Hence, these are our forward recurrences for the coefficients:

(10) $\begin{equation*} \begin{cases} x_1 = 1\\ x_2 = 0\\ x_{k+2} = x_k - q_k x_{k+1}, & k \geq 1 \end{cases} \qquad \text{ and } \qquad \begin{cases} y_1 = 0\\ y_2 = 1\\ y_{k+2} = y_k - q_k y_{k+1}, & k \geq 1 \end{cases} \end{equation*}$

We start from $\boldsymbol{a_1}$ and $\boldsymbol{a_2}$ and gradually work our way through division steps until we calculate the GCD, at which point we also obtain the sought Bézout’s coefficients:

This is how it’ll look like step by step:

This iterative form of the EEA is equivalent to the Blankinship method for two numbers, which extends EA to find the GCD and Bézout’s coefficients of $n \geq 2$ numbers, not just two.

5.1. Example

Let’s reuse the example for REEA. Here, we compute the coefficients as we perform Euclidean divisions. The first remainder, $34$ , is a direct linear combination of $254$ and $44$ :

Next, we divide $44$ with $34$ . Then, we express the remainder $10$ as a linear combination of $44$ and $34$ and replace $34$ with the expression we got in the previous step:

We obtain the coefficients repeating the step. After each division step, we express the remainder in terms of the current dividend and the divisor. Since both have appeared as remainders previously, we replace them with the corresponding linear combinations and simplify the expressions:

W get the same result as with REEA in the end, but without recursion. Generally, the iterative variant should be faster because it avoids recursive calls and keeps the same frame.

5.2. Speeding up the Algorithm

As we see from the recurrences (10), the $x$ -coefficients and $y$ -coefficients don’t depend on one another. Moreover, from the final form:

$GCD(a, b) = x\cdot a + y \cdot b$

we can calculate the final $y$ if we know the final $x$ :

$y = \frac{GCD(a,b)-x\cdot a}{b}$

and the other way around. So, there’s no need to compute both coefficients as we make division steps. That cuts the number of operations by a third.

6. How Many Coefficients Are There?

The Bézout’s coefficients are not unique, In fact, if $(x, y)$ is one pair of Bézout’s coefficients for $a$ and $b$ , then all the coefficients are of the form:

(11) $\begin{equation*} \left(x+k\left\lfloor\frac{a}{b}\right\rfloor, y + k\left\lfloor\frac{a}{b}\right\rfloor\right)\quad k \in Z \end{equation*}$

where $d=GCD(a, b)$ .

Only two pairs satisfy:

(12) $\begin{equation*} (|x| \leq |b/d|) \land (|y| \leq |a/d|) \end{equation*}$

and EEA always finds one such pair.

7. Conclusion

In this article, we presented the recursive and iterative forms of the Extended Euclidean Algorithm. It’s used for finding Bézout’s coefficients of two integer numbers and has applications in cryptography.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex