## 2.4   The Euclidean Algorithm 2

### 2.4.1   Finding One Solution

Your conjecture in Research Question 2 gives conditions that c must satisfy in order for

a x + b y = c

to have solutions. Suppose that c does 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 that a = 408, b = 126, and c = gcd(408, 126) = 6. Are there any solutions to the equation

408x + 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:

Your browser does not support java.

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

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

Now we just repeat:

Your browser does not support java.

Therefore, 126 = 4 ·30 + 6.

Your browser does not support java.

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

408x + 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 to

408x + 126y = 6.

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

Your browser does not support java.

Let's look at another example. Suppose that a = 1232 and b = 573, and we want to find a solution to

1232x + 573y = d,

where d = gcd(1232, 573). First we compute d using the Euclidean Algorithm:

Your browser does not support java.
1. 1232 = 2 ·573 + 86.

Your browser does not support java.
2. 573 = 6 ·86 + 57.

Your browser does not support java.
3. 86 = 1 ·57 + 29.

Your browser does not support java.
4. 57 = 1 ·29 + 28.

Your browser does not support java.
5. 29 = 1 ·28 + 1.

Your browser does not support java.
6. 28 = 28 ·1 + 0.

We see that d = gcd(1232, 573) = 1, and so we are looking for a solution to

1232x + 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 and y = –43 should be a solution to 1232x + 573y = 1. As before, let's check:

Your browser does not support java.

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: The GCD 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 to a x + b y = 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 the reverse Euclidean Algorithm method? Let's go with a simple example,

7x + 2y = 1.

It's clear that gcd(7, 2) = 1, and we get the solution x0= 1, y0 = –3 by reversing the steps of the Euclidean Algorithm. One way to look for other solutions is to perform a simple search. Solving for y in terms of x, we get the equation

y = (1 – 7x)/2.

If we plug in an integer value of x, and the corresponding value of y is 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 to ax + by = c, using values of x satisfying –n x n. Try it out on our example equation.

Your browser does not support java.

As you can see, our solution x0= 1, y0 = –3 is among those found. Let's try a different equation, say

8x + 3y = 1.

In this case, it's easy to see that gcd(8, 3) = 1, and the Euclidean Algorithm yields the solution x0= –1, y0 = 3. Solving for y in terms of x, we have y = (1 – 8x)/3. Here's the computation:

Your browser does not support java.

Looks fine. As you might guess, we are working towards forming a conjecture. Here's one more sample equation: 11x + 3y = 1. As we can see, gcd(11, 3) = 1, and the Euclidean Algorithm produces the solution x0= –1, y0 = 4. Here's the computation:

Your browser does not support java.

#### Research Question 3

Suppose that gcd(a, b) = 1, and that (x0, y0) is the solution to

ax + by = 1

produced by the Euclidean Algorithm. Find a general formula for all solutions (x, y) to the above equation, giving x in terms of x0 and y in terms of y0. Be sure to prove that your formula works and that it accounts for all solutions.

#### Research Question 4

Now suppose that gcd(a, b) = d > 1, and that (x0, y0) is the solution to

ax + by = d

produced by the Euclidean Algorithm. Find a general formula for all solutions (x, y) to the above equation, giving x in terms of x0 and y in terms of y0.
Hint: The equations ax + by = d and (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