Integer Solutions to AX + BY = C

Date: 04/25/2000 at 12:01:33
From: Carol
Subject: Algebraic equation with 2 variables

How do you prove that, for any equation of the form ax + by = c, where 
a, b and c are whole numbers, there will be an infinite number of 
whole number solutions for both x and y? (There is an exception to 
this - see next paragraph.) For example, the equation 4x + 7y = 30 is 
true for x (-3, 4, ...) and y (6, 2, ...). I have a feeling that for 
ANY values of a, b and c, there must exist an infinite number of cases 
where both x and y are whole numbers.

However, there are important exceptions to this. For example, the 
equation 2x + 4y = 65 cannot have whole number solutions for both x 
and y, since the sum of multiples of 2 must be even, and 65 is odd. 
This would be true for any equation in which a is a multiple of b (or 
vice versa), and c is not a multiple of either a or b. Apart from this 
situation, however, is it indeed the case that there exist an infinite 
number of whole number solutions for both x and y simultaneously in 
any equation ax + by = c? If so, how would you prove this?

Thanks for your help.

Carol

Date: 04/25/2000 at 13:07:04
From: Doctor Rob
Subject: Re: Algebraic equation with 2 variables

Thanks for writing to Ask Dr. Math, Carol.

Your intuition is correct. Whenever there is a solution, there are 
infinitely many.

Let d = GCD(a,b), the greatest common divisor of a and b. Then if d is 
not a divisor of c, there is no solution. If d is a divisor of c, 
there are solutions, and if (X,Y) is one solution, then all solutions 
have the form

     x = X + (b/d)*t
     y = Y - (a/d)*t

where t is any integer.

Thus there are infinitely many solutions whenever there are any. You 
can check this by substituting these into the equation and seeing that 
all the terms involving t drop out, and what is left is just the 
statement that (X,Y) is a solution.

If d does divide c, then you can divide d out of the equation to 
obtain

     (a/d)*x + (b/d)*y = c/d

and GCD(a/d,b/d) = 1. To find the one solution (X,Y), you can first 
solve

     (a/d)*x + (b/d)*y = 1

This is done by using the Extended Euclidean Algorithm starting with 
the two numbers a/d and b/d. If (x0,y0) is one solution to that 
equation, then X = (c/d)*x0, Y = (c/d)*y0, is one solution to the 
original equation. Again, this is easy to check.

If you want to know more about the use of the Extended Euclidean 
Algorithm to solve A*x + B*y = 1 with GCD(A,B) = 1, write again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 04/26/2000 at 15:05:23
From: J. Alfred Prufrock
Subject: Re: Algebraic equation with 2 variables

Dear Dr. Rob,

Thank you very much for your help. I have a couple of questions about 
what you said though. I hope they're not too silly.

1) Why is it that if GCD(a,b) is divisible by c, there must be 
solutions? I can see why there WON'T be solutions if GCD(a,b) is not 
divisible by c, but what guarantees that there will be solutions if it 
is? Is it because a multiple, say m, of a number can always be 
expressed as the sum of two multiples of m?

2) What about when GCD(a,b) = 1? Is a solution guaranteed for the same 
reason? (In this case m = 1, and any multiple of 1 can be expressed as 
the sum of two other multiples of 1?)

3) Why do I first have to solve (a/d)*x + (b/d)*y = 1 in order to 
solve the original equation a*x + b*y = c?

And yes, if you don't mind I would like to know more about using the 
Extended Euclidean Algorithm to solve A*x + B*y = 1.

Sorry if the above questions are stupid; I am learning all this on my 
own and have no one else to ask!

Thanks very much,
Carol

Date: 04/26/2000 at 17:16:11
From: Doctor Rob
Subject: Re: Algebraic equation with 2 variables

Thanks for writing back.

The only silly question is the one that isn't asked!

1) There are solutions when d divides c because they can be 
constructed using the techniques described above and below.

2) When d = 1, it automatically divides c, so there are always 
solutions. They are constructed using the technique described below.

3) You solve (a/d)*x + (b/d)*y = 1 first because we know how to do 
that easily, and by doing it, we can solve the original equation 
easily. It is just a matter of breaking down an originally 
hard-looking problem into smaller, more manageable pieces. This is not 
the only way to solve such problems, just a systematic method that 
always works.

Suppose you have two nonzero integers A and B. Then this is the 
Euclidean Algorithm:

     1. Start with two nonzero integers A and B.
     2. Express A = q*B + r, q and r integers with 0 <= r < |B|.
        (Do this using division with remainder.)
     3. If r = 0, output |B| and stop.
     4. Replace (A,B) by (B,r).
     5. Go to Step 2 above.

When you do this, the algorithm will output GCD(A,B) and stop.

Now the Extended Euclidean Algorithm is similar, but you compute more 
numbers as you go along:

     1. Start with two nonzero integers A and B, and set
        (u,U) = (1,0) and (v,V) = (0,1).
     2. Express A = q*B + r, q and r integers with 0 <= r < |B|.
     3. If r = 0, output |B|, U, and V, and stop.
     4. Replace (A,B) by (B,r), (u,U) by (U,u-q*U), and (v,V) by
        (V,v-q*V).
     5. Go to Step 2 above.

When you do this, the algorithm will output GCD(A,B), U, and V, and 
the following equation will be true:

     A*U + B*V = GCD(A,B).

Now when GCD(A,B) = 1, you get the solution x = U, y = V, of the 
equation

     A*x + B*y = 1.

Example: Solve 323*x + 256*y = 1. Solution, using the Extended 
Euclidean Algorithm:

     1. (A,B) = (323,256), (u,U) = (1,0), (v,V) = (0,1).
     2. 323 = 1*256 + 67, so q = 1, r = 67.
     3. Continue.
     4. (A,B) = (256,67), (u,U) = (0,1), (v,V) = (1,-1).
     2. 256 = 3*67 + 55, so q = 3, r = 55.
     3. Continue.
     4. (A,B) = (67,55), (u,U) = (1,-3), (v,V) = (-1,4).
     2. 67 = 1*55 + 12, so q = 1, r = 12.
     3. Continue.
     4. (A,B) = (55,12), (u,U) = (-3,4), (v,V) = (4,-5).
     2. 55 = 4*12 + 7, so q = 4, r = 7.
     3. Continue.
     4. (A,B) = (12,7), (u,U) = (4,-19), (v,V) = (-5,24).
     2. 12 = 1*7 + 5, so q = 1, r = 5.
     3. Continue.
     4. (A,B) = (7,5), (u,U) = (-19,23), (v,V) = (24,-29).
     2. 7 = 1*5 + 2, so q = 1, r = 2.
     3. Continue.
     4. (A,B) = (5,2), (u,U) = (23,-42), (v,V) = (-29,53).
     2. 5 = 2*2 + 1, so q = 2, r = 1.
     3. Continue.
     4. (A,B) = (2,1), (u,U) = (-41,107), (v,V) = (53,-135).
     2. 2 = 2*1 + 0, so q = 2, r = 0.
     3. Output (1,107,-135) and stop.

Now

     323*107 - 256*135 = 34561 - 34560 = 1

so the solution is (107,-135).

Example: Solve 323*x + 256*y = 179. From the previous example, we know 
that

     323*107 + 256*(-135) = 1.

Thus

     323*(107*79) + 256*(-135*79) = 79

so one solution is (107*79,-135*79) = (8453,-10665). Then the general 
solution is

     x = 8453 - 256*t
     y = -10665 + 323*t

for any integer t.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/