Using Bezout's identity

557 Views Asked by At

After obtaining $gcd(96,40)=8=5\times40-2\times96$

I don't understand how to continue the following question:

Does the equation $96x+40y=16$ have integer solutions $(x,y)$? If yes, find them all. Answer the same question with $96x+40y=5$.

The answer is yes for the first one because 8 divides 16 and the range is $(-4+5n,10-12n)$, no for the second one.

How do I get this?

1

There are 1 best solutions below

4
On BEST ANSWER

Recall that the equation $aX + bY = c$ with integers $a,b,c$ has integral solutions if and only if $d = \gcd(a,b) \mid c$.

If $(X_0,Y_0)$ is such that $aX_0 + bY_0 = d$, then the set of solutions in case $c = dc'$ is given by $$\{(c'X_0 + k (b/d) , c'Y_0 - k (a /d )) \colon k \in \mathbb{Z}\}.$$

You have $a=96$ and $b=40$. You found a GCD of $8$. Since $8 \mid 16$ you have solutions for $c=16$ and since $8 \nmid 5$ you have no solutions for $c= 5$.