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:
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
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
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.
Let's look at another example. Suppose that a = 1232 and b = 573, and we want to find a solution to
where d = gcd(1232, 573). First we compute d using 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 to
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:
Solving the linear equation
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
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,
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
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.
As you can see, our solution x0= 1, y0 = –3 is among those found. Let's try a different equation, say
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:
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:
Research Question 3Suppose that gcd(a, b) = 1, and that (x0, y0) is the solution to 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 4Now suppose that gcd(a, b) = d > 1, and that (x0, y0) is the solution to 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.
|