The Euclidean Algorithm

The following is Euclidean algorithm. Given two positive integers $𝑎$ and $𝑏$ , find $\gcd (𝑎,𝑏)$ .

Algorithm 3.1

Euclidean algorithm

Input: $𝑎,𝑏\in {\mathbb{Z}}^{+}$
Output: $\gcd (𝑎,𝑏)$

1	while $𝑏>0$ do
2	$𝑟←𝑎\operatorname{mod}𝑏$	// $0\leq 𝑟<𝑏$
3	$𝑎←𝑏$
4	$𝑏←𝑟$
5	return $𝑎$

Proof

The variables $𝑎$ and $𝑏$ change. Write ${𝑎}_{0}$ and ${𝑏}_{0}$ for the two inputs. At the start of each iteration, just before the guard on line 1 is tested, let $𝑃$ be the assertion that $𝑎>0$ , $𝑏\geq 0$ , and $\gcd (𝑎,𝑏)=\gcd ({𝑎}_{0},{𝑏}_{0})$ .

Initialization. Before the first iteration, $𝑎={𝑎}_{0}$ and $𝑏={𝑏}_{0}$ , both positive. Thus $𝑃$ holds.

Maintenance. Assume $𝑃$ holds before an iteration and the guard holds, so $𝑏>0$ . By Theorem 1.5 there is an integer $𝑞$ with $𝑎=𝑞𝑏+𝑟$ and $0\leq 𝑟<𝑏$ . Line 2 sets $𝑟$ to that remainder. By Theorem 3.2, $\gcd (𝑏,𝑟)=\gcd (𝑎,𝑏)$ . Lines 3 and 4 then replace $(𝑎,𝑏)$ by $(𝑏,𝑟)$ , in that order, so $𝑎$ receives the old value of $𝑏$ before $𝑏$ receives $𝑟$ . The new $𝑎$ is positive and the new $𝑏$ is nonnegative, and $𝑃$ holds at the next test of the guard.

Termination. Whenever the guard holds, line 2 produces $0\leq 𝑟<𝑏$ , and line 4 sets $𝑏$ equal to $𝑟$ . If the guard holds again, this new $𝑏$ is a strictly smaller positive integer. The successive values of $𝑏$ at the guard are therefore a strictly decreasing sequence of positive integers. If the sequence were infinite, its set of values would be a nonempty subset of ${\mathbb{Z}}^{+}$ with no least element, contradicting the well-ordering principle. So the guard fails after finitely many iterations.

Exit. The guard has failed and $𝑃$ still holds, so $𝑏\geq 0$ forces $𝑏=0$ , and $𝑎>0$ . Thus $𝑎$ divides both $𝑎$ and $0$ , and no larger positive integer divides $𝑎$ , hence $\gcd (𝑎,0)=𝑎$ . By $𝑃$ , line 5 returns $\gcd ({𝑎}_{0},{𝑏}_{0})$ .

The Euclidean algorithm can take quite a few steps. Given any positive integer $𝑛$ , there are integers $𝑎$ and $𝑏$ for which it runs exactly $𝑛$ steps to find $\gcd (𝑎,𝑏)$ . And $𝑛$ can be large, so the algorithm can feel slow.

Consecutive Fibonacci numbers are such examples.

Example 3.2

Apply the Euclidean algorithm to ${𝑓}_{10}=55$ and ${𝑓}_{9}=34$ :

\begin{aligned}55 & =34\cdot 1+21, \\ 34 & =21\cdot 1+13, \\ 21 & =13\cdot 1+8, \\ 13 & =8\cdot 1+5, \\ 8 & =5\cdot 1+3, \\ 5 & =3\cdot 1+2, \\ 3 & =2\cdot 1+1, \\ 2 & =1\cdot 2+0.\end{aligned}

That is $8$ steps, and the value returned is $1$ , so $\gcd ({𝑓}_{9},{𝑓}_{10})=1$ .

We have the general result:

Theorem 3.7

Consider the Fibonacci sequence

\{{𝑓}_{𝑛}\}

with

{𝑓}_{0}=0

and

{𝑓}_{1}=1

. For every integer

𝑛\geq 2

, the Euclidean algorithm takes exactly

𝑛

steps to show that

\gcd ({𝑓}_{𝑛+1},{𝑓}_{𝑛+2})=1

Note that this theorem does not only illustrate our point, that for every such $𝑛$ we can find an example on which the Euclidean algorithm runs for exactly $𝑛$ steps. Along the way it also proves that the consecutive Fibonacci numbers ${𝑓}_{𝑛+1}$ and ${𝑓}_{𝑛+2}$ are coprime: their greatest common divisor is $1$ .

From Example 3.2 we already have the idea of the proof. At every step except the last, the quotient is $1$ . At the last step the quotient is $2$ , and the remainder is $0$ .

Proof

By the recurrence of the Fibonacci sequence, for every integer $𝑘\geq 2$ ,

{𝑓}_{𝑘+2}={𝑓}_{𝑘+1}+{𝑓}_{𝑘}.

Note that $0<{𝑓}_{𝑘}<{𝑓}_{𝑘+1}$ . This is the crucial point: it shows that ${𝑓}_{𝑘+2}$ divided by ${𝑓}_{𝑘+1}$ has quotient $1$ and remainder ${𝑓}_{𝑘}$ . By Theorem 1.5, that quotient and remainder are unique.

So the Euclidean algorithm gives

\begin{aligned}{𝑓}_{𝑛+2} & ={𝑓}_{𝑛+1}\cdot 1+{𝑓}_{𝑛}, \\ {𝑓}_{𝑛+1} & ={𝑓}_{𝑛}\cdot 1+{𝑓}_{𝑛-1}, \\ & ⋮ \\ {𝑓}_{4} & ={𝑓}_{3}\cdot 1+{𝑓}_{2}, \\ {𝑓}_{3} & ={𝑓}_{2}\cdot 2+0.\end{aligned}

The algorithm returns ${𝑓}_{2}=1$ , which means $\gcd ({𝑓}_{𝑛+1},{𝑓}_{𝑛+2})=1$ . And it takes $𝑛$ steps.

The Complexity of the Euclidean Algorithm

We can prove a theorem of Gabriel Lamé: an upper bound on the number of steps the Euclidean algorithm takes.

Theorem 3.8Lamé's theorem

The number of divisions needed to find the greatest common divisor of two positive integers by the Euclidean algorithm does not exceed five times the number of decimal digits in the smaller of the two integers.

Mathematically, suppose $𝑎,𝑏\in {\mathbb{Z}}^{+}$ with $𝑎>𝑏$ , and suppose it takes $𝑛$ steps to find $\gcd (𝑎,𝑏)$ . Then $𝑛\leq 5𝑚$ , where $𝑚$ is the number of decimal digits of $𝑏$ .

The result is a nice one. We finally have an upper bound on the worst case of the Euclidean algorithm. At the same time the conclusion is baffling. What do decimal digits have to do with it, and where does the coefficient $5$ come from?

And you’d be surprised that the proof uses the Fibonacci sequence, and a property of it that we introduced, (1.8).

Proof

Suppose it takes $𝑛$ steps. Let ${𝑟}_{0}=𝑎$ and ${𝑟}_{1}=𝑏$ . The Euclidean algorithm gives

\begin{aligned}{𝑟}_{0} & ={𝑟}_{1}\cdot {𝑞}_{1}+{𝑟}_{2}, \\ {𝑟}_{1} & ={𝑟}_{2}\cdot {𝑞}_{2}+{𝑟}_{3}, \\ & ⋮ \\ {𝑟}_{𝑛-2} & ={𝑟}_{𝑛-1}\cdot {𝑞}_{𝑛-1}+{𝑟}_{𝑛}, \\ {𝑟}_{𝑛-1} & ={𝑟}_{𝑛}\cdot {𝑞}_{𝑛}+0.\end{aligned}

Since ${𝑞}_{𝑘}\geq 1$ ,

{𝑟}_{𝑘-1}\geq {𝑟}_{𝑘}+{𝑟}_{𝑘+1},\quad \forall 𝑘=1,\ldots ,𝑛-1.

(3.6)

Note

From (3.6) we should at once think of the recurrence for the Fibonacci sequence:

{𝑓}_{𝑛}={𝑓}_{𝑛-1}+{𝑓}_{𝑛-2}.

This is where the Fibonacci sequence first shows itself.

Now ${𝑟}_{𝑛}\geq 1={𝑓}_{2}$ , and ${𝑟}_{𝑛-1}>{𝑟}_{𝑛}$ , so ${𝑟}_{𝑛-1}\geq 2={𝑓}_{3}$ . It then follows that

\begin{aligned}{𝑟}_{𝑛-2} & \geq {𝑟}_{𝑛-1}+{𝑟}_{𝑛}\geq {𝑓}_{3}+{𝑓}_{2}={𝑓}_{4}, \\ {𝑟}_{𝑛-3} & \geq {𝑟}_{𝑛-2}+{𝑟}_{𝑛-1}\geq {𝑓}_{4}+{𝑓}_{3}={𝑓}_{5}, \\ & ⋮ \\ {𝑟}_{1} & \geq {𝑟}_{2}+{𝑟}_{3}\geq {𝑓}_{𝑛}+{𝑓}_{𝑛-1}={𝑓}_{𝑛+1}.\end{aligned}

In summary, we have an estimate for $𝑏$ by a Fibonacci number indexed from the number of steps taken:

𝑏={𝑟}_{1}\geq {𝑓}_{𝑛+1}.

Using (1.8), we have

𝑏\geq {𝑓}_{𝑛+1}>{\varphi }^{𝑛-1}.

At this point we already have the inequality that relates $𝑛$ . Taking the logarithm base $10$ , we move $𝑛-1$ from the exponent down into a product:

(𝑛-1){\log }_{10}\varphi <{\log }_{10}𝑏.

Suppose $𝑏$ has $𝑚\in {\mathbb{Z}}^{+}$ decimal digits. Then $𝑏<{10}^{𝑚}$ , and hence ${\log }_{10}𝑏<𝑚$ . Therefore

𝑛<\frac{𝑚}{{\log }_{10}\varphi }+1.

We can show that

{\log }_{10}\varphi >\frac{1}{5},

and then obtain

𝑛<\frac{𝑚}{{\log }_{10}\varphi }+1<\frac{𝑚}{\frac{1}{5}}+1=5𝑚+1.

That is where the $5$ comes from. Since $𝑛$ is an integer, $𝑛\leq 5𝑚$ .

Note

We could, of course, use a calculator to check ${\log }_{10}\varphi >\frac{1}{5}$ and be done. But I find the estimate itself interesting.

The idea is to show ${\varphi }^{5}>10$ . Recall that we have

{\varphi }^{2}=\varphi +1.

\begin{aligned}{\varphi }^{5} & ={({\varphi }^{2})}^{2}\cdot \varphi \\ & ={(\varphi +1)}^{2}\cdot \varphi \\ & =({\varphi }^{2}+2\varphi +1)\cdot \varphi \\ & =(3\varphi +2)\cdot \varphi \\ & =5\varphi +3.\end{aligned}

And

\varphi =\frac{1+\sqrt{5}}{2}>\frac{1+\sqrt{4}}{2}=\frac{3}{2},

{\varphi }^{5}=5\varphi +3>\frac{21}{2}=10.5>10.

Thus we obtain the estimate ${\log }_{10}\varphi >\frac{1}{5}$ .

Expressing Greatest Common Divisors as Linear Combinations

Question: how do we express the gcd, $𝑑$ , as a linear combination of $𝑎$ and $𝑏$ ?

We can trace the Euclidean algorithm backward, as it is described in the original textbook. The divisions are

\begin{aligned}{𝑟}_{0} & ={𝑟}_{1}\cdot {𝑞}_{1}+{𝑟}_{2}, \\ {𝑟}_{1} & ={𝑟}_{2}\cdot {𝑞}_{2}+{𝑟}_{3}, \\ & ⋮ \\ {𝑟}_{𝑛-3} & ={𝑟}_{𝑛-2}\cdot {𝑞}_{𝑛-2}+{𝑟}_{𝑛-1}, \\ {𝑟}_{𝑛-2} & ={𝑟}_{𝑛-1}\cdot {𝑞}_{𝑛-1}+{𝑟}_{𝑛}, \\ {𝑟}_{𝑛-1} & ={𝑟}_{𝑛}\cdot {𝑞}_{𝑛}+0,\end{aligned}

where ${𝑟}_{𝑛}=𝑑=\gcd (𝑎,𝑏)$ .

Every step but the last leaves a remainder, and that remainder can be moved to the other side of the equation. The second-to-last step is the one whose remainder is $𝑑$ itself. You see, we have

𝑑={𝑟}_{𝑛}={𝑟}_{𝑛-2}-{𝑟}_{𝑛-1}\cdot {𝑞}_{𝑛-1},

(3.7)

and so $𝑑$ is already a linear combination of ${𝑟}_{𝑛-2}$ and ${𝑟}_{𝑛-1}$ .

The step before that does the same for ${𝑟}_{𝑛-1}$ :

{𝑟}_{𝑛-1}={𝑟}_{𝑛-3}-{𝑟}_{𝑛-2}\cdot {𝑞}_{𝑛-2}.

Thus ${𝑟}_{𝑛-1}$ is a linear combination of the two terms that precede it, ${𝑟}_{𝑛-3}$ and ${𝑟}_{𝑛-2}$ . Substitute this expression into (3.7). What was a combination of ${𝑟}_{𝑛-2}$ and ${𝑟}_{𝑛-1}$ becomes a combination of ${𝑟}_{𝑛-3}$ and ${𝑟}_{𝑛-2}$ :

𝑑=-{𝑟}_{𝑛-3}{𝑞}_{𝑛-1}+(1+{𝑞}_{𝑛-2}{𝑞}_{𝑛-1}){𝑟}_{𝑛-2}.

And so on. Each time, the latest remainder still standing in the expression is rewritten, by the division that produced it, as a combination of two earlier ones. We keep working backward until the only numbers left are ${𝑟}_{0}=𝑎$ and ${𝑟}_{1}=𝑏$ . By then we are expressing $𝑑$ as a linear combination of $𝑎$ and $𝑏$ .

The problem seems solved. But if you think about writing a program to find the coefficients $𝑠$ and $𝑡$ such that

\gcd (𝑎,𝑏)=𝑠𝑎+𝑡𝑏,

then you will realize that this argument does not hand you $𝑠$ and $𝑡$ on the way down. The quotients appear only as the divisions are performed, and the backward steps need them in reverse: ${𝑞}_{1},{𝑞}_{2},\ldots ,{𝑞}_{𝑛-1}$ . One pass runs the Euclidean algorithm and stores those quotients. Another pass starts from $𝑑$ and walks back to $𝑎$ and $𝑏$ , building the coefficients as it goes. Two passes, and a list that has to sit there until the second one is finished. An uncomfortable feeling of wasting both time and space.

There is another way to look at the same divisions, a forward view.

\begin{aligned}{𝑟}_{0} & ={𝑟}_{1}\cdot {𝑞}_{1}+{𝑟}_{2} & \quad ⟺\quad & & {𝑟}_{2} & ={𝑟}_{0}-{𝑟}_{1}\cdot {𝑞}_{1}, \\ {𝑟}_{1} & ={𝑟}_{2}\cdot {𝑞}_{2}+{𝑟}_{3} & \quad ⟺\quad & & {𝑟}_{3} & ={𝑟}_{1}-{𝑟}_{2}\cdot {𝑞}_{2}, \\ & ⋮ & & & & ⋮ \\ {𝑟}_{𝑛-3} & ={𝑟}_{𝑛-2}\cdot {𝑞}_{𝑛-2}+{𝑟}_{𝑛-1} & \quad ⟺\quad & & {𝑟}_{𝑛-1} & ={𝑟}_{𝑛-3}-{𝑟}_{𝑛-2}\cdot {𝑞}_{𝑛-2}, \\ {𝑟}_{𝑛-2} & ={𝑟}_{𝑛-1}\cdot {𝑞}_{𝑛-1}+{𝑟}_{𝑛} & \quad ⟺\quad & & {𝑟}_{𝑛} & ={𝑟}_{𝑛-2}-{𝑟}_{𝑛-1}\cdot {𝑞}_{𝑛-1}, \\ {𝑟}_{𝑛-1} & ={𝑟}_{𝑛}\cdot {𝑞}_{𝑛}+0. & & & & \end{aligned}

(3.8)

Take a minute and think. Do you get what I mean?

Yes. Think this way. The right-hand column is the same division, solved for the new remainder. At the first step, ${𝑟}_{2}$ is a linear combination of ${𝑟}_{0}=𝑎$ and ${𝑟}_{1}=𝑏$ . At the second step, ${𝑟}_{3}$ is a linear combination of ${𝑟}_{1}$ and ${𝑟}_{2}$ . We can already write ${𝑟}_{2}$ in terms of $𝑎$ and $𝑏$ , and ${𝑟}_{1}$ is $𝑏$ , so replacing ${𝑟}_{2}$ writes ${𝑟}_{3}$ in terms of $𝑎$ and $𝑏$ as well. Each new remainder is a combination of the two that precede it, and those two are already combinations of $𝑎$ and $𝑏$ , so the new one is too. Keep going. It is the same replacement every time, and at the end $𝑑={𝑟}_{𝑛}$ is a linear combination of $𝑎$ and $𝑏$ .

Nothing has to be saved for a later pass. The quotient is used when it appears, to rewrite the new remainder, and then we do not need it again. One pass through the Euclidean algorithm, and no list of $𝑞$ ’s. This is, basically, the idea of the extended Euclidean algorithm.

Call the coefficients ${𝑠}_{𝑗}$ and ${𝑡}_{𝑗}$ , so that

{𝑟}_{𝑗}={𝑠}_{𝑗}𝑎+{𝑡}_{𝑗}𝑏.

From (3.8) we can read off the first two:

\begin{aligned}{𝑟}_{2} & ={𝑟}_{0}-{𝑟}_{1}\cdot {𝑞}_{1}=𝑎-{𝑞}_{1}𝑏 & ⟹\quad & & {𝑠}_{2}=1,\quad {𝑡}_{2}=-{𝑞}_{1}, \\ {𝑟}_{3} & ={𝑟}_{1}-{𝑟}_{2}\cdot {𝑞}_{2}=-{𝑞}_{2}𝑎+(1+{𝑞}_{1}{𝑞}_{2})𝑏 & ⟹\quad & & {𝑠}_{3}=-{𝑞}_{2},\quad {𝑡}_{3}=1+{𝑞}_{1}{𝑞}_{2}.\end{aligned}

We can fill in the definitions for $𝑗=0$ and $𝑗=1$ . We have

\begin{aligned}{𝑟}_{0} & =1\cdot {𝑟}_{0}+0\cdot {𝑟}_{1}, \\ {𝑟}_{1} & =0\cdot {𝑟}_{0}+1\cdot {𝑟}_{1},\end{aligned}

{𝑠}_{0}=1,\quad {𝑠}_{1}=0,\quad {𝑡}_{0}=0,\quad {𝑡}_{1}=1.

With ${𝑟}_{𝑗}={𝑠}_{𝑗}𝑎+{𝑡}_{𝑗}𝑏$ in hand, the recurrence for $\{{𝑠}_{𝑗}\}$ and $\{{𝑡}_{𝑗}\}$ is easy to derive. Suppose

\begin{aligned}{𝑟}_{𝑗-2} & ={𝑠}_{𝑗-2}𝑎+{𝑡}_{𝑗-2}𝑏, \\ {𝑟}_{𝑗-1} & ={𝑠}_{𝑗-1}𝑎+{𝑡}_{𝑗-1}𝑏.\end{aligned}

The next step is to express ${𝑟}_{𝑗}$ in $𝑎$ and $𝑏$ . From the Euclidean algorithm,

{𝑟}_{𝑗}={𝑟}_{𝑗-2}-{𝑟}_{𝑗-1}{𝑞}_{𝑗-1}.

Substitute ${𝑟}_{𝑗-2}$ and ${𝑟}_{𝑗-1}$ , and we obtain

{𝑟}_{𝑗}=({𝑠}_{𝑗-2}-{𝑞}_{𝑗-1}{𝑠}_{𝑗-1})𝑎+({𝑡}_{𝑗-2}-{𝑞}_{𝑗-1}{𝑡}_{𝑗-1})𝑏.

Matching coefficients gives

\begin{aligned}{𝑠}_{𝑗} & ={𝑠}_{𝑗-2}-{𝑞}_{𝑗-1}{𝑠}_{𝑗-1}, \\ {𝑡}_{𝑗} & ={𝑡}_{𝑗-2}-{𝑞}_{𝑗-1}{𝑡}_{𝑗-1},\end{aligned}

for $2\leq 𝑗\leq 𝑛$ . The cases $𝑗=2$ and $𝑗=3$ hold under the definitions just made for $𝑗=0$ and $𝑗=1$ .

Theorem 3.9

Let $𝑎,𝑏\in {\mathbb{Z}}^{+}$ with $𝑎>𝑏$ , and let $𝑛$ be the number of steps the Euclidean algorithm takes on $𝑎$ and $𝑏$ . Let ${𝑞}_{𝑗}$ be the quotients in that algorithm, and define ${𝑠}_{𝑗}$ and ${𝑡}_{𝑗}$ by

\begin{gathered}{𝑠}_{0}=1,\quad {𝑡}_{0}=0, \\ {𝑠}_{1}=0,\quad {𝑡}_{1}=1,\end{gathered}

and, for $2\leq 𝑗\leq 𝑛$ ,

\begin{aligned}{𝑠}_{𝑗} & ={𝑠}_{𝑗-2}-{𝑞}_{𝑗-1}{𝑠}_{𝑗-1}, \\ {𝑡}_{𝑗} & ={𝑡}_{𝑗-2}-{𝑞}_{𝑗-1}{𝑡}_{𝑗-1}.\end{aligned}

Then

\gcd (𝑎,𝑏)={𝑠}_{𝑛}𝑎+{𝑡}_{𝑛}𝑏.

Proof

Let ${𝑟}_{0}=𝑎$ , ${𝑟}_{1}=𝑏$ , and let ${𝑟}_{2},\ldots ,{𝑟}_{𝑛}$ be the later remainders, so ${𝑟}_{𝑛}=\gcd (𝑎,𝑏)$ and, by (3.8),

{𝑟}_{𝑗}={𝑟}_{𝑗-2}-{𝑟}_{𝑗-1}{𝑞}_{𝑗-1}

for $2\leq 𝑗\leq 𝑛$ . Let $𝑃(𝑗)$ be the assertion that ${𝑟}_{𝑗}={𝑠}_{𝑗}𝑎+{𝑡}_{𝑗}𝑏$ .

Base case. The values ${𝑠}_{0}=1$ , ${𝑡}_{0}=0$ , ${𝑠}_{1}=0$ , and ${𝑡}_{1}=1$ give ${𝑟}_{0}=1\cdot 𝑎+0\cdot 𝑏$ and ${𝑟}_{1}=0\cdot 𝑎+1\cdot 𝑏$ . Thus $𝑃(0)$ and $𝑃(1)$ hold. There are two base cases because the recurrence looks back two steps.

Inductive step. Let $2\leq 𝑗\leq 𝑛$ , and assume $𝑃(𝑗-2)$ and $𝑃(𝑗-1)$ . Then

\begin{aligned}{𝑟}_{𝑗} & ={𝑟}_{𝑗-2}-{𝑟}_{𝑗-1}{𝑞}_{𝑗-1} \\ & =({𝑠}_{𝑗-2}𝑎+{𝑡}_{𝑗-2}𝑏)-{𝑞}_{𝑗-1}({𝑠}_{𝑗-1}𝑎+{𝑡}_{𝑗-1}𝑏) \\ & =({𝑠}_{𝑗-2}-{𝑞}_{𝑗-1}{𝑠}_{𝑗-1})𝑎+({𝑡}_{𝑗-2}-{𝑞}_{𝑗-1}{𝑡}_{𝑗-1})𝑏 \\ & ={𝑠}_{𝑗}𝑎+{𝑡}_{𝑗}𝑏,\end{aligned}

where the last step is the recurrence. Thus $𝑃(𝑗)$ holds.

By induction, $𝑃(𝑗)$ holds for every $𝑗$ with $0\leq 𝑗\leq 𝑛$ . In particular, $𝑃(𝑛)$ is $\gcd (𝑎,𝑏)={𝑠}_{𝑛}𝑎+{𝑡}_{𝑛}𝑏$ .

In a program, we can use the following, the so-called extended Euclidean algorithm, to express $\gcd (𝑎,𝑏)$ as a linear combination of $𝑎$ and $𝑏$ .

Algorithm 3.2

Extended Euclidean algorithm

Input: $𝑎,𝑏\in {\mathbb{Z}}^{+}$
Output: $\gcd (𝑎,𝑏)$ , $𝑠$ , $𝑡$

1	$({𝑠}_{0},{𝑠}_{1})←(1,0)$
2	$({𝑡}_{0},{𝑡}_{1})←(0,1)$
3	while $𝑏>0$ do
4	$𝑞,𝑟←\operatorname{divmod}(𝑎,𝑏)$
5	$𝑎←𝑏$
6	$𝑏←𝑟$
7	$({𝑠}_{0},{𝑠}_{1})←({𝑠}_{1},{𝑠}_{0}-𝑞{𝑠}_{1})$
8	$({𝑡}_{0},{𝑡}_{1})←({𝑡}_{1},{𝑡}_{0}-𝑞{𝑡}_{1})$
9	return $𝑎$ , ${𝑠}_{0}$ , ${𝑡}_{0}$