Solve Equation Problem: 5x+6y=40 - Help & Hints

[Marin]

Hi there!

I have to solve the following equation:

5x+6y = 40

and find out every pair (x,y) from Z that satisfies the equation!

I would use the Chinese remainder theorem, if the RHS were 1 and not 40, but now I somehow got stuck!


Could someone please give me a hint :)


Thanks a lot in advance!

Marine

 

[dodo]

For an equation like ax + by = c, the gcd(a,b) must divide c in order for a solution to exist.

So the usual method is
1) use the Euclidean Algorithm for the gcd,
2) work it backwards to express the gcd as a linear combination of a and b,
and 3) multiply the identity in 2) by some integer that transform the gcd into c (such integer exists, if the gcd divides c)
This should give you an equation that expresses c as a linear combination of a and b.

Once you have one solution, there is some theorem somewhere that allows you to find all others.

Ref: D. Burton, "Elementary number theory", pp. 33-34.

 

[Marin]

ok, the gcd (5,6) = 1

1 = 5*(-1) +1*6

so I multiply by 40/1 = 40

this yields:

5x+6y = -5*40+6*40

but how am I supposed to get (x,y) from that?

 

[dodo]

You just got 40 = 5*(-40) + 6*40 . That looks a lot like 40 = 5x + 6y.

 

[Hurkyl]

Aside: how would you solve the problem if you were looking for all real solutions to that linear equation? While the little details might be different, the big picture is probably going to be similar (depending on how you actually solve it).

 

[Marin]

5x+6y = -5*40+6*40 :)

so the pair is (-40, 40)

ok, another one is (2,5) or also (-4, 10), but what do all these have in common hmmm?


Hurkyl, in R I would just express the one variable with the other to get a vector with parameter representing a line in R²: L = ((40-6y)/5 , y) = (8,0) + y(-6, 5) ...

..of course, now I could set y Element of Z and that should be it!


Thanks a lot, you two!

 

[Hurkyl]

Right -- most methods of doing this problem will reduce to finding a particular solution, and also the vector that allows you to change between solutions.

The extended Euclidean algorithm actually gives you both parts. Observe:


(6, 5)
(1, 5) : 1 = 1*6 + (-1)*5
(1, 0) : 0 = 1*5 + (-5)*1 = 6*5 + (-5)*6

And so scaling up gives you the particular solution: 5 * (-40) + 6 * 40 = 40
And the other vector gives you the delta: 5 * (-40 + 6*t) + 6 * (40 - 5*t) = 40

(Can you see an easier way to get the delta?)


To complicate the problem slightly, what if your target was 41 instead of 40? How many ways can you do the problem?

 

[soandos]

related, if gcd(x,y)=1, is there more than one solution for ax+by=1?

 

[cup]

There might be nicer ways of solving this problem.
(I am not very familiar with number theory.)

I found the following intuitive (inspired by Hurkyl):

The integer solutions of

(1): 5x + 6y = 40

are obviously a subset of the real solutions of the equation (a line).

We can find a single solution easily:

x₀ = 8 and y₀ = 0

The trick now is to use this solution to "start us of" as we scan for more solutions.

Basically, put (x₀, y₀) into (1).
Then perturb x₀ by 1 and y₀ by some number d (probably not an integer) so as to make the equation still hold. That is: you should solve for d, after you perturb.

Then d will be rational. Now figure out how many times you have to make that same perturbation in order to make d an integer.

Then you can write down a formula for (x_n, y_n) for any integer n, which generates all solutions.
Edit: I realize now that I didn't add much, you probably already cracked it. The formula is (x_n, y_n) = (8+6n, -5n), if you want to check your findings.

 

[Marin]

yes, cup, and this is exactly the vector Hurkyl meant with the free parameter as integer :)

but what if the free parameter is smaller than the coefficients before y, x:


5x + 6y = 4

then the vector should read: L = (4/5, 0) + y (-6, 5)

and it´s the 4/5 that does not allow us to produce integers from the vector for every integer y

 

[dodo]

Right - the fact that 5 divided 40 was just a way of getting a simple initial solution of the form (n, 0).

But if it doesn't, just find an initial solution by any other means, Euclidean or not. For example, since 6-5 = 1, it follows that (-a, a) is a solution for 5x + 6y = a.

 

[HallsofIvy]

If x₀ and y₀ are integer solutions of the equation ax+ by= c, then so is x= x₀+ bk and y= y₀- ak for any integer k.

That is easily shown just by putting them into the equation: ax+ by= a( x₀+ bk)+ b(y₀- ak)= ax₀+ abk+ by₀- abk= ax<sup>0[/sub]+ b₀= c because "abk" and "-abk" cancel.

In the case of the equation 5x+ 6y= 40, you had solutions x= -40 and y= 40. Then x= -40+ 6k and y= 40- 5k are also solutions. If, for example, you were looking for the smallest positive solutions, you would note that, because 6(6)= 36< 40 and 6(7)= 42> 40, k must be at least 7 in order that x be positive. Taking k= 7 gives x= -40+ 42= 2 and y= 40- 35= 5.</sup>

 

[arildno]

I'm no number theorist, and I realize that for general solutions, some clever, but long, algorithm might be needed.

However for this problem, it is fairly trivial:
We rewrite our equation as:
$$y=\frac{5(8-x)}{6}$$
Now, since 6 is not a divisor of 5, it has to be a divisor of 8-x, if y is to be an integer.
But that means x must be written as 8-6m, where m is an arbitrary integer, whereby y is trivially computed to be 5m.


(My "m" equals cup's "-n")

 

[cup]

yes, cup, and this is exactly the vector Hurkyl meant with the free parameter as integer :)

but what if the free parameter is smaller than the coefficients before y, x:5x + 6y = 4

then the vector should read: L = (4/5, 0) + y (-6, 5)

and it´s the 4/5 that does not allow us to produce integers from the vector for every integer y

It still works. Perhaps my description was not so clear.

Suppose that we have a solution (x₀, y₀), that is:

5x₀ + 6y₀ = 4

Now perturb the way I described, defining d so that the following equation holds:

5(x₀ + 1) + 6(y₀ + d) = 4

Solve for d:

d = -5/6

The order of 5 in Z₆ is k = 6/gcd(5,6) = 6.
(k is then the smallest number of times you must do the perturbation to get an integer for the y-component).

So the n'th solution is just the initial solution (x₀, y₀), perturbed kn times:

x_n = x₀ + kn = x₀ + 6n
y_n = y₀ + kdn = y₀ - 5n

 

[Hurkyl]

Now, for a fun bit of integer linear algebra!

The usual methods for solving the equation run into a bit of a snag, because you cannot row echelonize the augmented matrix
$$\left[ \begin{array}{cc|c}5 & 6 & 40 \end{array} \right]$$
because dividing by 5 is not an integer operation. So how do we do things systematically?

First off, it's usually easier to find nullvectors than to solve systems of equations, so let's rewrite the problem as wanting to find solutions to
$$\left[ \begin{array}{ccc}-40 & 5 & 6 \end{array} \right]<br /> \left[ \begin{array}{c}1 \\ x \\ y \end{array} \right] = [0]$$

and now, we can apply one of our trusty techniques: augment our matrix with an identity and column echelonize!
$$\left[ \begin{array}{ccc}-40 & 5 & 6 \\<br /> \hline<br /> 1 & 0 & 0 \\<br /> 0 & 1 & 0 \\<br /> 0 & 0 & 1<br /> \end{array} \right]$$

well, we like row operations better than column operations, so let's transpose.

$$\left[ \begin{array}{c|ccc}<br /> -40 & 1 & 0 & 0 \\<br /> 5 & 0 & 1 & 0 \\<br /> 6 & 0 & 0 & 1<br /> \end{array} \right]$$

Recall that the point of this is if I do row reduction to reduce this matrix to

$$\left[ \begin{array}{c|ccc}<br /> 1 & a & b & c \\<br /> 0 & 1 & d & e \\<br /> 0 & 0 & 1 & f<br /> \end{array} \right]$$

then I know that

$$\left[ \begin{array}{ccc}<br /> a & b & c \\<br /> 1 & d & e \\<br /> 0 & 1 & f<br /> \end{array} \right]<br /> \left[ \begin{array}{c} -40 & 5 & 6<br /> \end{array} \right]<br /> =<br /> \left[ \begin{array}{c} 1 & 0 & 0<br /> \end{array} \right]$$

from which I can immediately read off the solution to my problem:

-40 * x + 5 * (dx + y) + 6 (ex + fy) = 0

or after fixing x to 1:

5(d + y) + 6(e + fy) = 40

The only snag: how to perform row reduction, if we're not allowed to divide rows by an integer? Well, we're lucky this time; we won't need it. By row permuting:

$$\left[ \begin{array}{c|ccc}<br /> 6 & 0 & 0 & 1 \\<br /> 5 & 0 & 1 & 0 \\<br /> -40 & 1 & 0 & 0<br /> \end{array} \right]$$

and adding multiples of the second row to the first and third:

$$\left[ \begin{array}{c|ccc}<br /> 1 & 0 & -1 & 1 \\<br /> 5 & 0 & 1 & 0 \\<br /> 0 & 1 & 8 & 0<br /> \end{array} \right]$$

and of the first to the second

$$\left[ \begin{array}{c|ccc}<br /> 1 & 0 & -1 & 1 \\<br /> 0 & 0 & 6 & -5 \\<br /> 0 & 1 & 8 & 0<br /> \end{array} \right]$$

permute again

$$\left[ \begin{array}{c|ccc}<br /> 1 & 0 & -1 & 1 \\<br /> 0 & 1 & 8 & 0 \\<br /> 0 & 0 & 6 & -5<br /> \end{array} \right]$$

and reduce a bit more

$$\left[ \begin{array}{c|ccc}<br /> 1 & 0 & 5 & -4 \\<br /> 0 & 1 & 2 & 5 \\<br /> 0 & 0 & 6 & -5<br /> \end{array} \right]$$

We have no way to reduce that 6 to a 1, but that's fine: it turns out that this is the standard form of the matrix:
. Each pivot is positive
. Each number below a pivot is zero
. Each number above a pivot is nonnegative, and less than the pivot

So, this gives us the solution:
40 = 5(2 + 6t) + 6(5 - 5t)

The other vector, incidentally, tells is the collective GCD of everything:
1 = -40 * 0 + 5 * 5 + 6 * (-4)
in linear algebra terminology, 1 is the basis for the lattice spanned by -40, 5, and 6. (A lattice is, roughly speaking, a vector space over the integers) If we had had more equations, we'd be in a higher dimensional space, and things would look less trivial.



But I never did answer how to deal with the fact that scaling a row isn't an invertible row operation -- it turns out that you don't need it! The Euclidean algorithm tells you exactly what to do to reduce your matrix. For example, to reduce

$$\left[ \begin{array}{cc}<br /> 5 & 3 \\<br /> 7 & 8<br /> \end{array} \right]$$

I would subtract the first from the second:

$$\left[ \begin{array}{cc}<br /> 5 & 3 \\<br /> 2 & 5<br /> \end{array} \right]$$

twice the second from the first

$$\left[ \begin{array}{cc}<br /> 1 & -7 \\<br /> 2 & 5<br /> \end{array} \right]$$

and twice the first from the second

$$\left[ \begin{array}{cc}<br /> 1 & -7 \\<br /> 0 & 19<br /> \end{array} \right]$$

Don't be tempted to do something like "replace the second row with 3 times the first row minus twice the second row" -- that secretly involves scaling operations. The corresponding row matrix is

$$\left[ \begin{array}{cc}<br /> 1 & 0 \\<br /> 3 & -2<br /> \end{array} \right]$$

which is an invertible real matrix, but not an invertible integer matrix! To do that operation, you actually have to compensate by doing the row operations corresponding to

$$\left[ \begin{array}{cc}<br /> 1 & -1 \\<br /> 3 & -2<br /> \end{array} \right]$$
instead: this is invertible. (Its determinant is 1)



So anyways, here's an exercise: find all integer solutions to the system of equations

5x + 6y + 7z = 10
7x - 3y + 2z = 6

 

[cup]

So anyways, here's an exercise: find all integer solutions to the system of equations

5x + 6y + 7z = 10
7x - 3y + 2z = 6

Answer: there are none.
Correct?

I used a quick and dirty approach. It was only a few lines.

It would be an interesting exercise find an algorithm for the general case of m linear equations and n unknowns, but I'm sure there is already such an algorithm out there.

 

[Hurkyl]

Oh I'm going to be so embarassed if you're right. That'll teach me not to actually solve the problem before proposing it as an exercise! *gets to work*

Yah, it looks like you're right. The system is inconsistent modulo 3, because it reduces to:

-x + z = 1 (mod 3)
x - z = 0 (mod 3)

which clearly has no solutions.


Okay, new problem:

5x + 6y + 7z = 30
7x - 3y + 2z = 18


(Of course, the previous exercise wasn't a bad one -- it's important to know how to prove a system has no solutions. It's just not what I was intending to do. )

 

[cup]

Okay, new problem:

5x + 6y + 7z = 30
7x - 3y + 2z = 18

Answer:

x_n = 11n
y_n = 13n-2
z_n = 6-19n

where n is any integer.
Correct?