Solvability of a certain equation

[Bipolarity]

Homework Statement

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$$

Homework Equations

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

 

[Dick]

Homework Statement

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$$

Homework Equations

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

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

 

[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

 

[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.

 

[Ray Vickson]

Homework Statement

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$$

Homework Equations

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

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.

 

[Chestermiller]

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