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!

How do you solve 5x + 9y = 181?

  1. Oct 8, 2014 #1
    Sorry for the misleading title. My question is: how do you solve Xa + Yb = Z, where X, Y, and Z are positive integer constants and a and b are positive integer variables?

    For example, consider 5x + 9y = 181. The problem is: solve for all possible answers for x and y, where x and y are both positive integers. Is it just trial and error or is there some equation that would lead me directly to all the solutions?
     
  2. jcsd
  3. Oct 8, 2014 #2

    Mark44

    Staff: Mentor

    Look up Diophantine equation (http://en.wikipedia.org/wiki/Diophantine_equation) and the Chinese remainder theorem.
     
  4. Oct 8, 2014 #3

    jtbell

    User Avatar

    Staff: Mentor

    Not if a and b are both required to be integers.
     
  5. Oct 8, 2014 #4
    I noticed in the particular example I proposed that the solutions to y are those integers that differ from 9 by a multiple of 5 (or zero). Thus, the solutions to y are 4, 9, 14, and 19 which is an arithmetic progression modulo 5. As far as x goes, it seems a little more tricky: x differs from 5 by integers that are multiples of 3, which is a divisor of 9. 9 seems to be the limiting agent here.
     
  6. Oct 8, 2014 #5
    Oh, duh.......all the x's are in an arithmetic progression congruent 2 modulo 9: 2, 11, 20, 29. Why it starts at 2 is a little perplexing.
     
  7. Oct 9, 2014 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    As an example, for the equation 5x+ 9y= 181, 5 divides into 9 once with remainder 4: 9- 5= 4. 4 divides into 5 once with remainder 1: 5- 4= 1. Replacing the "4" in that last equation with 9- 5, 5- (9- 5)= 5(2)+ 9(-1)= 1. Multiply both sides of the equation by 181: 5(362)+ 9(-181)= 181. Thus x= 362, y= -181 is a solution. But it is easy to see that x= 362- 9k, y= -181+ 5k is also a solution for any integer k: 5(362- 9k)+ 9(-181+ 5k)= 5(362)- 45k- 9(181)+ 45k= 5(362)- 9(181)= 181.

    In particular, if x and y are required to be positive, we must have -181+ 5k> 0 so 5k> 181, k> 36; as well as 362- 9k> 0 so 9k< 362, k< 41. Taking k= 37 gives x= 362- 9(37)= 29, y= -181+ 5(37)= 4. Taking k= 38, x= 362- 9(38)= 20, y= -181+ 5(38)= 9. Taking k= 39, x= 362- 9(39)= 11, y= -181+ 5(39)= 14. Taking k= 40, x= 362- 9(40)= 2, y= -181+ 5(40)= 19. Values of k less than 37 make y negative, values of k larger than 40 make x negative.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook