The Euclidean algorithm, which is used to find the greatest common divisor of two integers, can be extended to solve linear Diophantine equations. (Our textbook, Problem Solving Through Recreational Mathematics, describes a different method of solving linear Diophantine equations on pages 127–137.)

Long division of two integers (called the dividend and the divisor—the dividend is the number which is to be divided by the divisor) produces a quotient and a remainder. The relationship between these four numbers is described algebraically in the theorem below (found in the textbook on page 120).

Theorem 4.7. (Division algorithm.) Given any two positive integers

nandd, there exist integersqandr(respectively called the quotient and the remainder) such that

n=qd+rand 0 ≤r<d.

[This theorem is commonly called the “division algorithm,” even
though it isn’t really an *algorithm* in the sense of a sequence
of steps to follow. The real “division algorithm” is the steps
followed in the process of long division, for instance; the theorem above can
be seen as a consequence of this process.]

For example, let’s consider the division algorithm applied to the
numbers `n` = 101 and `d` = 8. When we
divide 101 by 8, we get a quotient of 12 and a remainder of 5.
[With a calculator: 101 ÷ 8 = 12.625, so the
quotient, after we drop the decimal part, is 12, and the remainder is
101 − 12(8) = 5.] Note that the remainder
`r` = 5 satisfies the inequality
0 ≤ `r` < 8, and we can write the
dividend 101 in terms of the quotient 12, the divisor 8, and the
remainder 5 as follows:

101 = 12(8) + 5.

In the discussion of the extended Euclidean algorithm below, we will find it more useful to rewrite this equation to express the remainder in terms of the dividend, the quotient, and the divisor. For example, with the numbers used above, we can write

5 = 101 − 12(8).

In general, if the remainder is `r`, the dividend
is `n`, the quotient is `q`, and the divisor
is `d`, we can write

`r` = `n` − `q``d`.

The Euclidean algorithm is usually used
simply to find the greatest common divisor of two integers. (For a description
of this algorithm, see the notes about additional topics
in number theory.) The standard Euclidean algorithm gives the greatest
common divisor and nothing else. However, if we keep track of a bit more
information as we go through the algorithm, we can discover how to write the
greatest common divisor as an integer linear combination of the two
original numbers. In other words, we can find integers `s`
and `t` such that

gcd(`a`, `b`) = `s``a` + `t``b`.

[Note that, since gcd(`a`, `b`) is usually less than
both `a` and `b`, one of `s`
or `t` will usually be negative.]

As a reminder, here are the steps of the standard Euclidean algorithm to
find the greatest common divisor of two positive integers `a`
and `b`:

- Set the value of the variable
`c`to the larger of the two values`a`and`b`, and set`d`to the smaller of`a`and`b`. - Find the remainder when
`c`is divided by`d`. Call this remainder`r`. - If
`r`= 0, then gcd(`a`,`b`) =`d`. Stop. - Otherwise, use the current values of
`d`and`r`as the new values of`c`and`d`, respectively, and go back to step 2.

The extended Euclidean algorithm uses the same framework, but there is a bit more bookkeeping. Before we present a formal description of the extended Euclidean algorithm, let’s work our way through an example to illustrate the main ideas.

Let’s take `a` = 1398 and
`b` = 324. We will proceed through the steps of the standard
Euclidean algorithm to find gcd(1398, 324), but we will keep track of more
information as we go. The main idea is to maintain, at every step, an
expression for `r` in terms of the original numbers `a`
and `b`. We can do this based on the division algorithm.

In our example, we begin (in step 1) with `c` = 1398
and `d` = 324. We continue to step 2. The quotient when
1398 is divided by 324, which we shall call `q`, is 4;
and the remainder, which we shall call `r`, is 102. [With a
calculator: 1398 ÷ 324 = 4.3148148, so we drop the
decimal part to get the quotient `q` = 4, and then the
remainder is
`r` = 1398 − 4(324) = 102.] Now,
by the division algorithm, we can write `r` in terms of
`c`, `q`, and `d`:

`r` = `c` − `q``d`.

In our case,

102 = 1398 − 4(324).

We want to maintain an expression for `r` in terms of the
original numbers `a` and `b`. Since
`a` = 1398 and `b` = 324, we rewrite the
expression above as

102 = `a` − 4`b`.

Let’s record in a table what we have done so far.

c | d | q | r | Conclusion | |
---|---|---|---|---|---|

Step 1 | 1398 | 324 | |||

Step 2 | 1398 | 324 | 4 | 102 | 102 = a − 4b |

We continue with the standard Euclidean algorithm. Since the
remainder `r` is not 0, we skip step 3 and go to
step 4. We use the current values of `d` and `r` as
the new values of `c` and `d`, respectively, and return
to step 2.

c | d | q | r | |
---|---|---|---|---|

Step 4 | 324 | 102 |

When 324 is divided by 102, the quotient is 3 and the remainder is 18. This means that

18 = 324 − 3(102).

This is an expression for the remainder `r`, but we would like
it to be in terms of the original numbers `a` and `b`.
Since `b` = 324, we can directly replace 324
with `b`. And from our previous work, we know how to write the
number 102 in terms of `a` and `b`. So we can
write

18 | = | 324 − 3(102) |

= | b − 3(a − 4b) | |

= | b − 3a + 12b | |

= | −3a + 13b. |

This gives us another row in our table.

c | d | q | r | Conclusion | |
---|---|---|---|---|---|

Step 2 | 324 | 102 | 3 | 18 | 18 = −3a + 13b |

Since `r` ≠ 0, we skip step 3 and go to
step 4. So we take the current values of `d`
and `r` and use them as the new values of `c`
and `d`, respectively.

c | d | q | r | |
---|---|---|---|---|

Step 4 | 102 | 18 |

Now we go back to step 2. When we divide 102 by 18, we get a quotient of 5 and a remainder of 12. So

12 = 102 − 5(18).

To write an expression for the remainder 12 in terms of `a`
and `b`, we use the expressions we have previously found for 102
and 18:

12 | = | 102 − 5(18) |

= | (a − 4b)
− 5(−3a + 13b) | |

= | a − 4b
+ 15a − 65b | |

= | 16a − 69b. |

We have another row in the table.

c | d | q | r | Conclusion | |
---|---|---|---|---|---|

Step 2 | 102 | 18 | 5 | 12 | 12 = 16a − 69b |

Again `r` ≠ 0, so we skip step 3 and go to
step 4, where we take the current values of `d`
and `r` and use them as the new values of `c`
and `d`.

c | d | q | r | |
---|---|---|---|---|

Step 4 | 18 | 12 |

We return to step 2. When 18 is divided by 12, the quotient is 1 and the remainder is 6. Thus

6 = 18 − 1(12).

Substituting the expressions for 18 and 12 that we have already found, we get

6 | = | 18 − 1(12) |

= | (−3a + 13b)
− 1(16a − 69b) | |

= | −3a + 13b
− 16a + 69b | |

= | −19a + 82b. |

So we can add the following row to our table.

c | d | q | r | Conclusion | |
---|---|---|---|---|---|

Step 2 | 18 | 12 | 1 | 6 | 6 = −19a + 82b |

Once again we have a remainder that is not 0, so we skip step 3
and go to step 4. The current values of `d` and `r`
become the new values of `c` and `d`.

c | d | q | r | |
---|---|---|---|---|

Step 4 | 12 | 6 |

Coming back to step 2, we divide 12 by 6 and see that the division
comes out evenly, with a quotient of 2 and a remainder of 0. If we
like, we can write an expression for 0 in terms of `a`
and `b` just as we have been doing:

0 | = | 12 − 2(6) |

= | (16a − 69b)
− 2(−19a + 82b) | |

= | 16a − 69b
+ 38a − 164b | |

= | 54a − 233b. |

Often we are not interested in an expression for 0; we are
interested in an expression for the greatest common divisor, which is the
remainder we got the *previous* time. So usually when we find that the
remainder is 0 we skip this algebra and go straight to step 3. However,
an expression for 0 is sometimes useful (we will see a use for it later).
So let’s record this expression for 0 in our table.

c | d | q | r | Conclusion | |
---|---|---|---|---|---|

Step 2 | 12 | 16 | 2 | 0 | 0 = 54a − 233b. |

Now that we have reached a remainder of 0, step 3 tells us that
the greatest common divisor is the current value of `d`
(that is, the previous value of `r`) and says to stop. In
our case, we have found that gcd(1398, 324) = 6, and we have an
expression for 6 in terms of the original numbers `a`
and `b`:

6 | = | −19a + 82b |

= | −19(1398) + 82(324). |

It is a good idea to check our work. We can use a calculator to quickly verify that −19(1398) + 82(324) = 6, so our arithmetic seems to check out.

Here is a summary of the whole process we just performed. A table such as this is probably the most efficient way to go through the extended Euclidean algorithm by hand.

c | d | q | r | Conclusion | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Step 1 | 1398 | 324 | |||||||||||||||

Step 2 | 1398 | 324 | 4 | 102 |
| ||||||||||||

Step 4 | 324 | 102 | |||||||||||||||

Step 2 | 324 | 102 | 3 | 18 |
| ||||||||||||

Step 4 | 102 | 18 | |||||||||||||||

Step 2 | 102 | 18 | 5 | 12 |
| ||||||||||||

Step 4 | 18 | 12 | |||||||||||||||

Step 2 | 18 | 12 | 1 | 6 |
| ||||||||||||

Step 4 | 12 | 6 | |||||||||||||||

Step 2 | 12 | 6 | 2 | 0 |
| ||||||||||||

Step 3 | gcd(1398, 324) = 6 = −19(1398) + 82(324) |

We can formally describe the process we used above. This process is called
the extended Euclidean algorithm. It is used for finding the
greatest common divisor of two positive integers `a`
and `b` and writing this greatest common divisor as an integer
linear combination of `a` and `b`. The steps of this
algorithm are given below.

- Set the value of the variable
`c`to the larger of the two values`a`and`b`, and set`d`to the smaller of`a`and`b`. - Find the quotient and the remainder when
`c`is divided by`d`. Call the quotient`q`and the remainder`r`. Use the division algorithm and expressions for previous remainders to write an expression for`r`in terms of`a`and`b`. - If
`r`= 0, then gcd(`a`,`b`) =`d`. The expression for the previous value of`r`gives an expression for gcd(`a`,`b`) in terms of`a`and`b`. Stop. - Otherwise, use the current values of
`d`and`r`as the new values of`c`and`d`, respectively, and go back to step 2.

A common use of the extended Euclidean algorithm is to solve a linear Diophantine equation in two variables. Such an equation is of the form

`a``x` + `b``y` = `c`,

where `x` and `y` are variables and
`a`, `b`, and `c` are constants. Most of
the work to solve an equation like this is performing the extended Euclidean
algorithm with the numbers `a` and `b`. After we have
completed the extended Euclidean algorithm, we have only a small step to take
to solve the Diophantine equation.

There are three cases to consider, which depend on the relationship between
`c` and gcd(`a`, `b`).

Let’s first consider the case in which
`c` = gcd(`a`, `b`). For instance,
suppose `a` = 1398, `b` = 324, and
`c` = 6:

1398`x` + 324`y` = 6.

From what we have already done, we know that 6 is the greatest common divisor of 1398 and 324, and in fact we have an expression for 6 in terms of 1398 and 324:

6 = −19(1398) + 82(324).

So `x` = −19, `y` = 82 is a
solution to the Diophantine equation above.

Thus we see that if
`c` = gcd(`a`, `b`), the extended
Euclidean algorithm will give us a solution for `x`
and `y` directly.

Suppose `c` is a multiple of gcd(`a`, `b`);
in particular, let’s say

`c` = `k` ⋅ gcd(`a`, `b`),

where `k` is an integer. Then we can find a solution to the
Diophantine equation
`a``x` + `b``y` = `c`
by writing gcd(`a`, `b`) in terms of `a`
and `b` and then multiplying the coefficients
by `k`.

For example, consider the Diophantine equation

1398`x` + 324`y` = 60.

We know that gcd(1398, 324) = 6, and from the extended Euclidean algorithm we know how to write 6 in terms of 1398 and 324:

6 = −19(1398) + 82(324).

However, the right-hand side of the equation we are considering is not 6 but 60. This is a multiple of 6; in particular, 60 = 10(6). We can use this to write 60 in terms of 1398 and 324:

60 | = | 10(6) |

= | 10[−19(1398) + 82(324)] | |

= | −190(1398) + 820(324). |

So `x` = −190, `y` = 820 is a
solution to this Diophantine equation. (Check this!)

In the previous two cases, we used the extended Euclidean algorithm to find
*one* solution to each Diophantine equation. But in fact these equations
have *infinitely many* solutions, and the extended Euclidean algorithm
can be used to generate as many of these solutions as we like.

The extended Euclidean algorithm, if carried out all the way to the end,
gives a way to write 0 in terms of the original numbers `a`
and `b`. We can add or subtract 0 as many times as we like
without changing the value of an expression, and this is the basis for
generating other solutions to a Diophantine equation, as long as we are given
one initial solution.

For example, when `a` = 1398 and
`b` = 324, we saw that the extended Euclidean algorithm
produces the expression

0 = 54`a` − 233`b`,

so

0 = 54(1398) − 233(324).

(This can easily be checked with a calculator.) Let’s consider again the Diophantine equation

1398`x` + 324`y` = 60.

Suppose we know one value of `x` and one value
of `y` that together form a solution to this equation. Since
0 = 54(1398) − 233(324), if we add 54
to `x` and subtract 233 from `y`, we will produce
another solution, because

1398(x + 54) + 324(y − 233) |
= | 1398x + 1398(54)
+ 324y + 324(−233) |

= | [1398x + 324y]
+ [1398(54) + 324(−233)] | |

= | 60 + 0. |

Similarly, we can subtract 54 from `x` and add 233
to `y` to get another solution to this Diophantine equation. In
general, we can add any multiple of 54 to `x` and subtract
the same multiple of 233 from `y`, or subtract any multiple
of 54 from `x` and add the same multiple of 233
to `y`, to produce another solution.

Above we found that `x` = −190,
`y` = 820 is a solution to the Diophantine equation
1398`x` + 324`y` = 60. From what we have
seen here, we know that we can get another solution by adding 54
to −190 and subtracting 233 from 820 to get another
solution:

x | = | −190 | + | 54 | = | −136, |

y | = | 820 | + | 233 | = | 587. |

So `x` = −136, `y` = 587 is also
a solution to this Diophantine equation. (Check this!) Additional solutions can
be found in a similar manner.

As we have seen in the previous two cases, the extended Euclidean algorithm
gives us a method to write any multiple of gcd(`a`, `b`)
in terms of integer multiples of `a` and `b`. But what
if we are attempting to solve a Diophantine equation
`a``x` + `b``y` = `c`
in which `c` is not a multiple of
gcd(`a`, `b`)? The extended Euclidean algorithm will be
of no use. Do we need to invent another method to handle this case?

As it turns out, the answer is no. If `c` is not a multiple of
gcd(`a`, `b`), then there are *no* integer
solutions to the equation
`a``x` + `b``y` = `c`.
So the extended Euclidean algorithm is all we need—it will give us all
integer solutions if any exist, and otherwise there are no integer solutions to
the Diophantine equation at all.

For example, suppose we have the Diophantine equation
4`x` + 6`y` = 1. [This equation shows up
in the analysis of Sample Problem 4.3(b) on pages 117–118 of the
textbook.] The greatest common divisor of 4 and 6 is 2, and 1 is
not a multiple of 2. So this Diophantine equation has no solutions. After
some thought, it should be clear why this is so: Whatever integers we choose
for `x` and `y`, the value of the left-hand side
4`x` + 6`y` must be even, but the right-hand side
is 1, which is odd.

Last updated 26 February 2010. Brian Kell <bkell@cmu.edu>