+78 A pair of positive integers (x, y) satisfies the equation 31x + 29y = 1125. What is x + y?
If we were to ignore the "positive numbers" phrase in the question, then we would use Euclid's algorithm and get 1125 = 29(16875) + 31(-15750). One of the numbers is negative, and they're quite large.
I also know that
If a×m + b×n = c
then (a - n)×m + (b+m)×n = c
If you work out the algebra,
(a - n)×m + (b+m)×n = c
am - nm + bm + mn = c
and since nm = mn, the equality is maintained.
But more importantly, the identify (an equation that is always true) allows you to reduce am and increase bm at the same time, by subtracting nm from am and adding mn to bm.
I'm unsure of how to use this to solve the problem.
