21-110: The extended Euclidean algorithm (2024)

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

The division algorithm

Long division of two integers (called the dividend and thedivisor—the dividend is the number which is to be divided bythe divisor) produces a quotient and a remainder. Therelationship between these four numbers is described algebraically in thetheorem below (found in the textbook on page120).

Theorem4.7. (Division algorithm.)Given any two positive integers n andd, there existintegers q andr (respectively called thequotient and the remainder) such that

n=qd+rand0≤r<d.

[This theorem is commonly called the “division algorithm,” eventhough it isn’t really an algorithm in the sense of a sequenceof steps to follow. The real “division algorithm” is the stepsfollowed in the process of long division, for instance; the theorem above canbe seen as a consequence of this process.]

For example, let’s consider the division algorithm applied to thenumbers n=101 and d=8. When wedivide 101 by8, we get a quotient of12 and a remainder of5.[With a calculator: 101÷8=12.625, so thequotient, after we drop the decimal part, is12, and the remainder is101−12(8)=5.] Note that the remainderr=5 satisfies the inequality0≤r<8, and we can write thedividend101 in terms of the quotient12, the divisor8, and theremainder5 as follows:

101=12(8)+5.

In the discussion of the extended Euclidean algorithm below, we will find itmore useful to rewrite this equation to express the remainder in terms of thedividend, the quotient, and the divisor. For example, with the numbers usedabove, we can write

5=101−12(8).

In general, if the remainder isr, the dividendisn, the quotient isq, and the divisorisd, we can write

r=n−qd.

Our goal

The Euclidean algorithm is usually usedsimply to find the greatest common divisor of two integers. (For a descriptionof this algorithm, see the notes about additional topicsin number theory.) The standard Euclidean algorithm gives the greatestcommon divisor and nothing else. However, if we keep track of a bit moreinformation as we go through the algorithm, we can discover how to write thegreatest common divisor as an integer linear combination of the twooriginal numbers. In other words, we can find integers sandt such that

gcd(a,b)=sa+tb.

[Note that, since gcd(a,b) is usually less thanboth a andb, one of sort will usually be negative.]

As a reminder, here are the steps of the standard Euclidean algorithm tofind the greatest common divisor of two positive integers aandb:

1. Set the value of the variablec to the larger of the twovalues a andb, andset d to the smaller of a andb.
2. Find the remainder when c is divided byd. Callthis remainderr.
3. If r=0, thengcd(a,b)=d. Stop.
4. Otherwise, use the current values of d andr asthe new values of c andd, respectively, and go backto step2.

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

An example

Let’s take a=1398 andb=324. We will proceed through the steps of the standardEuclidean algorithm to find gcd(1398,324), but we will keep track of moreinformation as we go. The main idea is to maintain, at every step, anexpression forr in terms of the original numbers aandb. We can do this based on the division algorithm.

In our example, we begin (in step1) with c=1398and d=324. We continue to step2. The quotient when1398 is divided by324, which we shall callq, is4;and the remainder, which we shall callr, is102. [With acalculator: 1398÷324=4.3148148, so we drop thedecimal part to get the quotient q=4, and then theremainder isr=1398−4(324)=102.] Now,by the division algorithm, we can writer in terms ofc,q, andd:

r=c−qd.

In our case,

102=1398−4(324).

We want to maintain an expression forr in terms of theoriginal numbers a andb. Sincea=1398 and b=324, we rewrite theexpression above as

102=a−4b.

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

We continue with the standard Euclidean algorithm. Since theremainderr is not0, we skip step3 and go tostep4. We use the current values of d andr asthe new values of c andd, respectively, and returnto step2.

When 324 is divided by102, the quotient is3 and the remainderis18. This means that

18=324−3(102).

This is an expression for the remainderr, but we would likeit to be in terms of the original numbers a andb.Since b=324, we can directly replace 324withb. And from our previous work, we know how to write thenumber102 in terms of a andb. So we canwrite

This gives us another row in our table.

Since r≠0, we skip step3 and go tostep4. So we take the current values of dandr and use them as the new values of candd, respectively.

Now we go back to step2. When we divide 102 by18, we get aquotient of5 and a remainder of12. So

12=102−5(18).

To write an expression for the remainder12 in terms of aandb, we use the expressions we have previously found for 102and18:

We have another row in the table.

Again r≠0, so we skip step3 and go tostep4, where we take the current values of dandr and use them as the new values of candd.

We return to step2. When 18 is divided by12, the quotientis1 and the remainder is6. Thus

6=18−1(12).

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

So we can add the following row to our table.

Once again we have a remainder that is not0, so we skip step3and go to step4. The current values of d andrbecome the new values of c andd.

Coming back to step2, we divide 12 by6 and see that the divisioncomes out evenly, with a quotient of2 and a remainder of0. If welike, we can write an expression for0 in terms of aandb just as we have been doing:

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

Now that we have reached a remainder of0, step3 tells us thatthe greatest common divisor is the current value ofd(thatis, the previous value ofr) and says to stop. Inour case, we have found that gcd(1398,324)=6, and we have anexpression for6 in terms of the original numbers aandb:

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

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

The extended Euclidean algorithm

We can formally describe the process we used above. This process is calledthe extended Euclidean algorithm. It is used for finding thegreatest common divisor of two positive integers aandb and writing this greatest common divisor as an integerlinear combination of a andb. The steps of thisalgorithm are given below.

1. Set the value of the variablec to the larger of the twovalues a andb, andset d to the smaller of a andb.
2. Find the quotient and the remainder when c is dividedbyd. Call the quotientq and theremainderr. Use the division algorithm and expressions forprevious remainders to write an expression forr in terms ofa andb.
3. If r=0, thengcd(a,b)=d. The expressionfor the previous value ofr gives an expression forgcd(a,b) in terms of aandb. Stop.
4. Otherwise, use the current values of d andr asthe new values of c andd, respectively, and go backto step2.

Solving linear Diophantine equations in two variables

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

ax+by=c,

where x andy are variables anda,b, andc are constants. Most ofthe work to solve an equation like this is performing the extended Euclideanalgorithm with the numbers a andb. After we havecompleted the extended Euclidean algorithm, we have only a small step to taketo solve the Diophantine equation.

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

Case1:c=gcd(a,b)

Let’s first consider the case in whichc=gcd(a,b). For instance,suppose a=1398, b=324, andc=6:

1398x+324y=6.

From what we have already done, we know that 6 is the greatest commondivisor of 1398 and324, and in fact we have an expression for6in terms of 1398 and324:

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

So x=−19, y=82 is asolution to the Diophantine equation above.

Thus we see that ifc=gcd(a,b), the extendedEuclidean algorithm will give us a solution for xandy directly.

Case2: c is a multiple ofgcd(a,b)

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 theDiophantine equationax+by=cby writing gcd(a,b) in terms of aandb and then multiplying the coefficientsbyk.

For example, consider the Diophantine equation

1398x+324y=60.

We know that gcd(1398,324)=6, and from the extendedEuclidean algorithm we know how to write6 in terms of 1398and324:

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

However, the right-hand side of the equation we are considering isnot6 but60. This is a multiple of6; in particular,60=10(6). We can use this to write60 in terms of 1398and324:

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

Aside: Generating more solutions

In the previous two cases, we used the extended Euclidean algorithm to findone solution to each Diophantine equation. But in fact these equationshave infinitely many solutions, and the extended Euclidean algorithmcan 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 write0 in terms of the original numbers aandb. We can add or subtract0 as many times as we likewithout changing the value of an expression, and this is the basis forgenerating other solutions to a Diophantine equation, as long as we are givenone initial solution.

For example, when a=1398 andb=324, we saw that the extended Euclidean algorithmproduces the expression

0=54a−233b,

so

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

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

1398x+324y=60.

Suppose we know one value ofx and one valueofy that together form a solution to this equation. Since0=54(1398)−233(324), if we add 54tox and subtract 233 fromy, we will produceanother solution, because

Similarly, we can subtract 54 fromx and add 233toy to get another solution to this Diophantine equation. Ingeneral, we can add any multiple of54 tox and subtractthe same multiple of233 fromy, or subtract any multipleof54 fromx and add the same multiple of233toy, to produce another solution.

Above we found that x=−190,y=820 is a solution to the Diophantine equation1398x+324y=60. From what we haveseen here, we know that we can get another solution by adding 54to−190 and subtracting 233 from820 to get anothersolution:

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

Case3: c is not a multiple ofgcd(a,b)

As we have seen in the previous two cases, the extended Euclidean algorithmgives us a method to write any multiple of gcd(a,b)in terms of integer multiples of a andb. But whatif we are attempting to solve a Diophantine equationax+by=cin which c is not a multiple ofgcd(a,b)? The extended Euclidean algorithm will beof 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 ofgcd(a,b), then there are no integersolutions to the equationax+by=c.So the extended Euclidean algorithm is all we need—it will give us allinteger solutions if any exist, and otherwise there are no integer solutions tothe Diophantine equation at all.

For example, suppose we have the Diophantine equation4x+6y=1. [This equation shows upin the analysis of Sample Problem4.3(b) on pages 117–118 of thetextbook.] The greatest common divisor of 4 and6 is2, and 1isnot a multiple of2. So this Diophantine equation has no solutions. Aftersome thought, it should be clear why this is so: Whatever integers we choosefor x andy, the value of the left-hand side4x+6y must be even, but the right-hand sideis1, which is odd.

Backto the 21-110 page