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 n and d, there exist integers q and r (respectively called the quotient and the remainder) such that
n = qd + r and 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 − qd.
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) = sa + tb.
[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:
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 − qd.
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 − 4b.
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.
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
ax + by = 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:
1398x + 324y = 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 ax + by = 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
1398x + 324y = 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 = 54a − 233b,
so
0 = 54(1398) − 233(324).
(This can easily be checked with a calculator.) Let’s consider again the Diophantine equation
1398x + 324y = 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 1398x + 324y = 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 ax + by = 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 ax + by = 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 4x + 6y = 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 4x + 6y must be even, but the right-hand side is 1, which is odd.