# Extended Euclidean Algorithm to find 2 POSITIVE Coefficients?

There's a problem I ran into that said:

"At a certain casino, blue poker chips are worth 9 dollars and white poker chips are worth 14 dollars. How many chips can Hank buy to spend exactly 206 dollars?"

The answer is 19 chips (12 blue and 7 white). The solution posed was trial-and-error which was frustrating. I was able to use an augmented matrix to solve it, but that took longer than I would've liked.

I noticed 9 and 14 are coprime, though, so according to the Euclidean Algorithm there exist integers X and Y such that 9X+14Y=1 (since gcd(9,14)=1). That said, there should be integers X' and Y' such that 9X'+14Y'=206 (linear independence; spanning set; etc.). The issue here is that 9X+14Y=1 results in X=-3, Y=2. Negative numbers aren't allowed in the question posed above, technically.

Is there any way to use the Extended Euclidean Algorithm to solve this problem such that we have X' and Y' BOTH positive? Or is it not possible using the Algorithm this way?

• If $X', Y'$ are to be both positive, $9X'+14Y'$ would be larger than $1$. – Wojowu Jul 17 '18 at 17:34

The issue here is that $9X+14Y=1$ results in $X=-3, Y=2$.
That's not the only solution. The coefficients in this linear combination are never unique, since you can always add any solution of $9a+14b=0$. In your case, you're starting with
$9 \times (-3) \times 206 + 14 \times 2 \times 206 = 206$
and your goal is to modify these coefficients so that they both become positive, by using whole multiples of $(-14,9)$. This can always be done as soon as the target number ($206$ here) is large enough. The official name for this result is the "Chicken McNugget Theorem", and it's what you need to know to solve most problems of this nature.
You know that $206-14Y\equiv-1+4Y\pmod9$ and you're after those $Y$'s such that this is congruent to $0$ modulo $9$. But\begin{align}-1+4Y\equiv0\pmod9&\iff4Y\equiv1\pmod9\\&\iff Y\equiv7\pmod9.\end{align}So, take $Y=7$ and $X=\frac{206-7\times14}9=12$.