# Homework Help: Solvability of a certain equation

1. Mar 18, 2013

### Bipolarity

1. The problem statement, all variables and given/known data
I am trying to determine whether, for a given integer Q , there always exist integers M,N that solve the following equation:
$$Q = 5N + 4M$$

2. Relevant equations

3. The attempt at a solution
For example, suppose Q=45. Will I definitely will be able to find M,N both integers, such that 5N+4M=45? Is this always possible? I think yes, but I'm trying to prove it. I could use some hints.

Thanks.

BiP

2. Mar 18, 2013

### Dick

5 and 4 are relatively prime. Is that enough of a hint?

3. Mar 18, 2013

### ehild

You can write the left-hand side in the form (4+1)N+4M=4(M+N)+N. So you have to find two integers P and N so as Q=4P + N...

ehild

4. Mar 19, 2013

### HallsofIvy

AM+ BN= Q has a solution as long as A and B are "relatively prime"- that is, they are not both divisible by the same number. If A and B are NOT relatively prime, let P be their "greatest common divisor". If Q is also divisible by P, divide each part by P to reduce to an equation that is solvable

If Q is not divisible by P then the left side, for any M and N, is a number having P as a factor and the right is not. They cannot be equal so the equation has no solution.

In this case, it is easy to see that 5- 4= 1. Multiply both sides by 45.

5. Mar 19, 2013

### Ray Vickson

If M and N are allowed to be < 0 as well as ≥ 0, then there is a solution for any integer Q ≥ 1. However, if M,N must be ≥ 0 then all you can say is that there is an integer Q0 ≥ 1 such that the equation has a solution for all Q ≥ Q0. You might try to find the smallest Q0 that "works" here.

6. Mar 20, 2013

### Staff: Mentor

This is the kind of problem we learned to do in High School on math team. It usually involves objects that can't be subdivided into smaller parts, so that a solution in terms of integers is required. For example, 5 times the number of boys in the class plus 4 time the number of girls in the class is equal to 45. How many boys and girls are there? You certainly can't chop them into fractions of boys and girls unless you want to get CSI NY involved. The way we learned it was to isolate the variable with the smallest coefficient on one side of the equation, and solve for that variable in terms of the other:

$$M = 11-N+\frac{1-N}{4}$$

The fraction in this equation must be an integer K:

$$N=1-4K$$

K =0, N=1, M = 10
K=-1, N=5, M = 5
K=-2, N=9, M = 0