Integer Solutions of ax + by = c, a, b,c, all integers
Solving equations of the form, ax + by = c, a, b,c, all integers , is not easy peasy. However, one of type of such equations is easy peasy. It is a linear Diophantine equation.
In general, linear Diophantine equations are solvable if and only if the greatest common divisor of a and b divides c.
A common way to find integer solutions of linear Diophantine equations is a method known as Euclidean algorithm (to find the gcd of a and b) in reverse.
Please have a go to succinct sayings and clear examples given by Dr Paul below. It is kindly acknowledged that the below information was inserted from his website: http://mathforum.org/dr.math/
Date: 04/04/2001 at 18:13:57
From: Doctor Paul
Subject: Re: integer solutions to ax+by = c
Solving equations of the form ax + by = c has been around for a long
time. The mathematician Diophantus of Alexandria (200-284 AD) gave a
general solution for when problems of this type are solvable. Of
course he was only interested in integer solutions, so when we say a
problem like this is solvable, we mean that there exist integers x and
y such that ax + by = c.
Because Diophantus showed when these equations are solvable, they are
today known as Diophantine equations. More specifically, they are
linear Diophantine equations.
In general, linear Diophantine equations are solvable if and only if
the greatest common divisor of a and b divides c. So this answers part
B in your question.
If you try to find integers x and y such that 3x + 6y = 4, you'll have
problems. Notice that gcd(3,6) = 3 and since 3 does not divide four,
the problem has no solution. You're welcome to try to find a
solution, but you'd be wasting your time.
If the linear Diophantine equation is solvable, there is an infinite
number of integer solutions. Here's how to solve them:
You first need to know the Euclidean algorithm for determining the gcd
of a and b. So let's do that. It's easiest to show an example of how
it works:
Let's say you want to find the gcd of 6 and 64.
Proceed as follows (the idea is a generalization of the division
algorithm):
64 = 10*6 + 4
6 = 1*4 + 2
4 = 2*2 + 0
When you get a zero in the "remainder" spot, you're done. The gcd is
the previous remainder. So in this case, the gcd of 6 and 64 is two.
Let's do another example:
Find the gcd of 12 and 136.
136 = 11*12 + 4
12 = 3*4 + 0
so the gcd of 12 and 136 is 4.
One of the things that Euclid showed is that you can express gcd(a,b)
as a linear combination of a and b. That is, there always exist
integers x and y such that ax + by = d, where d = gcd(a,b).
This is getting closer to what we want, but we're not quite there yet.
The way to find the integers x and y is to use the Euclidean algorithm
(which you just did to find the gcd of a and b) in reverse.
Let's go to 2
Solve for the gcd:
2 = 6 - 1*4
Now look at the next line up in your Euclidean algorithm:
64 = 10*6 + 4
Solve this for the remainder: 4 = 64 - 10*6. Now substitute this
expression of the number four into the last line we had: 2 = 6 - 1*4
2 = 6 - 1*4
2 = 6 - 1*(64 - 10*6)
2 = 6 - 64 + 10*6
2 = 11*6 - 64
We have found the desired integers.
So if we had been asked to find integers x and y such that
6x + 64y = 2, we could reply that x = 11 and y = -1 back to when we
found the gcd of 6 and 64. We said that was 2.
So that means we can find integers x and y such that 6x + 64y = 2.
Let's find them. Here's how to do it. Start with the next to the last
line in your Euclidean algorithm (the one that gave the gcd):
6 = 1*4 + 2
Solve for the gcd:
2 = 6 - 1*4
Now look at the next line up in your Euclidean algorithm:
64 = 10*6 + 4
Solve this for the remainder: 4 = 64 - 10*6. Now substitute this
expression of the number four into the last line we had: 2 = 6 - 1*4
2 = 6 - 1*4
2 = 6 - 1*(64 - 10*6)
2 = 6 - 64 + 10*6
2 = 11*6 - 64
We have found the desired integers.
So if we had been asked to find integers x and y such that 6x + 64y =
2, we could reply that x = 11 and y = -1.
Let's do another example like this.
Find integers x and y such that 12378x + 3054y = 6
Well, we first need to find gcd(12378,3054). It should be obvious at
this point that gcd(12378,3054) = 6 because I haven't told you how to
finish the problem if the right-hand side is not equal to gcd(a,b).
We proceed to find gcd(12378,3054):
12378 = 4*3054 + 162
3054 = 18*162 + 138
162 = 1*138 + 24
138 = 5*24 + 18
24 = 1*18 + 6
18 = 3*6 + 0
So gcd(12378,3054) is indeed 6.
Now write 6 as a linear combination of 12378 and 3054 by reversing the
steps of the Euclidean algorithm that was used to find the gcd.
6 = 24 - 18
= 24 - (138 - 5*24)
= 6*24 - 138
= 6(162-138) - 138
= 6*162 - 7*138
= 6*162 - 7(3054 - 18*162)
= 132*162 - 7*3054
= 132(12378 - 4*3054) - 7*3054
= 132*12378 + (-535)*3054
Thus x = 132 and y = -535
The French mathematician Gabriel Lame (1795-1870) proved that the
number of steps required in the Euclidean Algorithm is at most five
times the number of digits in the smaller integer. In this example,
the smaller integer (3054) has four digits, so the total number of
divisions cannot be greater than 20; in fact, only six divisions were
needed.
Now let's talk about what to do if asked to find integers x and y such
that ax + by = t, where t is not equal to gcd(a,b).
The procedure is exactly the same as the procedure outlined above, but
one extra step is needed. The extra step will become obvious as we
proceed. Let's look at an example:
172x + 20y = 1000
Using the Euclidean Algorithm, it is found that gcd(172,20) = 4.
I'll leave the work to you. Working backward to write 4 as a linear
combination of 172 and 20, we obtain:
4 = 2*172 + (-17)*20
Again, you supply the work.
We wanted to have something of the form 1000 = 172x + 20y.
Now the aforementioned extra step:
Do you see that if we take the equation 4 = 2*172 + (-17)*20 and
multiply both sides by 1000/4 = 250, we're done?
4 = 2*172 + (-17)*20
1000 = 500*172 + (-4250)*20
So we were asked to solve 172x + 20y = 1000. Clearly, x = 500 and
y = -4250.
Now let's go back to something I said in the beginning. I said that if
a set of integer solutions (x,y) existed, an infinite number of
integer solution pairs exist.
That is indeed the case.
If x = x_0 and y = y_0 are the initial solutions, then the family of
solutions is given by:
x = x_0 + (b/d)*t
y = y_0 - (a/d)*t
where d = gcd(a,b) and t is an arbitrary integer.
So here's an example of that idea. If you look at the linear
Diophantine equation 5x + 22y = 18, the initial solution is x = 8,
y = -1.
The complete solution is given by:
x = 8 + 22t
y = -1 - 5t
(You do the work.)
I hope this has been helpful. Please write back if you have additional
questions.
- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
No comments:
Post a Comment