Associated Topics || Dr. Math Home || Search Dr. Math

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?

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:

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:

(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/
```
Associated Topics:
High School Basic Algebra

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search