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

[David Carroll]

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?

 

[Mark44]

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?

Look up Diophantine equation (http://en.wikipedia.org/wiki/Diophantine_equation) and the Chinese remainder theorem.

 

[jtbell]

you can choose any b and get a corresponding a.

Not if a and b are both required to be integers.

 

[David Carroll]

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.

 

[David Carroll]

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.

 

[HallsofIvy]

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.