Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Integer Solutions of ax + by = c


Date: 04/03/2001 at 19:58:44
From: Chris Armentrout
Subject: integer solutions to ax+by = c

Dr. Math,

I am teaching a class to help prepare colleagues for the California 
Praxis exam. This question came up for us.  While we were able to find 
part A all right, we could not find the solution to the general 
solution.

A) Given the equation 5y - 3x = 1, find three points where x and y are 
   both integers.

B) Show that there will always be integer points (x,y) in ax + by = c 
   if a, b and c are all integers. If not, show a counterexample.

Thanks, I'm looking forward to your reply.

Chris Armentrout


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/   
    
Associated Topics:
College Discrete Math
College Number Theory
High School Discrete Mathematics
High School Linear Equations
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/