here for a more elementary working of a similar problem.
You take a 17 quart jug and a 12 quart jug to a stream, but you want to bring 8 quarts of water back. How do you do it?
Attempt at a solution
I used Bezout's Identity for this:
8 = 17x + 12y
However, the GCD of (12, 17) is 1. So:
1 = 17x' + 12y'
Using Bezout's Identity, I get:
x' = 5, y = -7
Therefore, x = 40, y = -56.
According to this result, I have to fill the 17 quart jug 40 times and pour into the 12 quart jug 56 times. That seems pretty excessive. Can anyone tell me what I'm doing wrong?
Look at it as which for our purposes we can rewrite . This means if we fill the small jug 10 times and empty everything into the large jug (we will have to empty the large jug 7 times in the process) we will be left with 1 quart left in the large jug. Similar holds for any other positive integers a and b where b < 17 and -- a is the number of times we fill the small jug, and b is the target.
And for completeness, .
Probably should have mentioned that we can also fill the large jug and empty into the small jug, in which case we need to fill it 4 times since .
Note that 4*17 - 5*12 = 8.
Might have reduced confusion if I'd mentioned this at the beginning, however my mindset was of filling the smaller jug because of the other thread I referenced.