## 2.4.1 Finding One Solution

Your conjecture in Research Question 2 gives conditions that

cmust satisfy in order for

ax+by=cto have solutions. Suppose that

cdoes have the form given in your conjecture; in this case, are we guaranteed that there will be solutions to our equation? This is a pretty general question. Let's look at one special case: suppose thata= 408,b= 126, andc= gcd(408, 126) = 6. Are there any solutions to the equation408

x+ 126y= 6?It turns out that the answer to this question is yes. To find a solution, we start by going through the steps of the Euclidean Algorithm to show that gcd(408, 126) = 6:

Therefore, 408 = 3 ·126 + 30. Remember that

gcd(408, 126) = gcd(126, 30).

Now we just repeat:

Therefore, 126 = 4 ·30 + 6.

Therefore, 30 = 5 ·6 + 0. Since clearly 30 is divisible by 6, then it follows that gcd(30, 6) = 6. Thus is must be that gcd(408, 126) = 6. Now, what does this have to do with solutions to

408

x+ 126y= 6?Good question. Let's take a look at the steps in the Euclidean Algorithm again:

(a) 408 = 3 ·126 + 30. (b) 126 = 4 ·30 + 6. (c) 30 = 5 ·6 + 0. Reorganizing the equation in step (b), we have

6 = 126 – (4 ·30). (3) From step (a), we see that 30 = 408 – (3 ·126). Substituting into equation (3), we get

6 = 126 – (4 ·30) = 126 – 4 ·(408 – 3 ·126) = (– 4) ·408 + (1 + 12) ·126 = (– 4) ·408 + 13 ·126 Therefore, we see that

x= – 4,y= 13 is a solution to408

x+ 126y= 6.

Just to be on the safe side, let's check using the on-line calculator.

Let's look at another example. Suppose that

a= 1232 andb= 573, and we want to find a solution to1232 x+ 573y=d,where

d= gcd(1232, 573). First we computedusing the Euclidean Algorithm:

1. 1232 = 2 ·573 + 86.

2. 573 = 6 ·86 + 57.

3. 86 = 1 ·57 + 29.

4. 57 = 1 ·29 + 28.

5. 29 = 1 ·28 + 1.

6. 28 = 28 ·1 + 0.We see that

d= gcd(1232, 573) = 1, and so we are looking for a solution to1232 x+ 573y= 1.Here's a summary of the above steps:

1. 1232 = 2 ·573 + 86. 2. 573 = 6 ·86 + 57. 3. 86 = 1 ·57 + 29. 4. 57 = 1 ·29 + 28. 5. 29 = 1 ·28 + 1. 6. 28 = 28 ·1 + 0. Now we work our way back up the chain:

1 = 29 – 1 ·28 = 29 – 1 ·(57 – 1 ·29) = –1 ·57 + 2 · 29 = –1 ·57 + 2 ·(86 – 1 ·57) = 2 ·86 – 3 ·57 = 2 ·86 – 3 ·(573 – 6 ·86) = –3 ·573 + 20 ·86 = –3 ·573 + 20 ·(1232 – 2 ·573) = 20 ·1232 – 43 ·573. So,

x= 20 andy= –43 should be a solution to 1232x+ 573y= 1. As before, let's check:Solving the linear equation

ax+by= gcd(a,b)is useful in a variety of places in number theory. Indeed, the fact that this equation always has a solution is so handy that we give it a special name:

TheGCD Trick. We'll have several opportunities to exploit the GCD Trick as the course progresses.

## 2.4.2 Finding All Solutions

So far, so good. The method that we used in the two previous examples is quite general, and will work to find a solution to any equation of the form

ax+by=d, (4)where

d= gcd(a,b). Although we have made some progress towards our original goal of finding all solutions toax+by=c, we still have a long way to go. The next question that we shall consider is the following: Are there any solutions to equation (4) other than the one guaranteed by the GCD Trick and found using thereverse Euclidean Algorithmmethod? Let's go with a simple example,7 x+ 2y= 1.It's clear that gcd(7, 2) = 1, and we get the solution

x_{0}= 1,y_{0}= –3 by reversing the steps of the Euclidean Algorithm. One way to look for other solutions is to perform a simple search. Solving foryin terms ofx, we get the equationy= (1 – 7x)/2.If we plug in an integer value of

x, and the corresponding value ofyis also an integer, then the pair (x,y) is a solution to our equation. (Be sure that you understand why before moving forward.) The applet below will do the computing. It searches for solutions toax+by=c, using values ofxsatisfying –nxn. Try it out on our example equation.

As you can see, our solution

x_{0}= 1,y_{0}= –3 is among those found. Let's try a different equation, say8 x+ 3y= 1.In this case, it's easy to see that gcd(8, 3) = 1, and the Euclidean Algorithm yields the solution

x_{0}= –1,y_{0}= 3. Solving foryin terms ofx, we havey= (1 – 8x)/3. Here's the computation:

Looks fine. As you might guess, we are working towards forming a conjecture. Here's one more sample equation: 11

x+ 3y= 1. As we can see, gcd(11, 3) = 1, and the Euclidean Algorithm produces the solutionx_{0}= –1,y_{0}= 4. Here's the computation:

## Research Question 3

Suppose that gcd(

a,b) = 1, and that (x_{0},y_{0}) is the solution toax+by= 1produced by the Euclidean Algorithm. Find a general formula for all solutions (

x,y) to the above equation, givingxin terms ofx_{0}andyin terms ofy_{0}. Be sure to prove that your formula works and that it accounts forallsolutions.

## Research Question 4

Now suppose that gcd(

a,b) =d> 1, and that (x_{0},y_{0}) is the solution toax+by=dproduced by the Euclidean Algorithm. Find a general formula for all solutions (

x,y) to the above equation, givingxin terms ofx_{0}andyin terms ofy_{0}.Hint:The equationsax+by=dand (a/d)x+ (b/d)y= 1 have the same set of solutions.

Section 2.1 | Section 2.2 | Section 2.3 | Section 2.4 | Section 2.5

Copyright © 2001 by W. H. Freeman and Company