1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Solvability of a certain equation

  1. Mar 18, 2013 #1
    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:
    [tex] Q = 5N + 4M [/tex]

    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.


  2. jcsd
  3. Mar 18, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    5 and 4 are relatively prime. Is that enough of a hint?
  4. Mar 18, 2013 #3


    User Avatar
    Homework Helper

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

  5. Mar 19, 2013 #4


    User Avatar
    Science Advisor

    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.
  6. Mar 19, 2013 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
  7. Mar 20, 2013 #6
    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:

    [tex]M = 11-N+\frac{1-N}{4}[/tex]

    The fraction in this equation must be an integer K:


    K =0, N=1, M = 10
    K=-1, N=5, M = 5
    K=-2, N=9, M = 0
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted