Solution of a given linear diophantine equation.

Question

I was solving the following linear diophantine equation :

$56x + 72y = 40 $ in integers.

My attempt: I got that 8 is the gcd of 56 and 72 and $8|40$ and hence a solution exists and I can write:

$8 = 56 - 16 *3 $

$\implies$ $ 8= 56 - (72 -56*1)*3$

$\implies$ $ 8= 4*56 - 3*72$.

So my answer is $x = 4$ and $y = -3$. But in book its showing $x = 20$ and $y = -15$. Where I went wrong? Kindly help.

Answer 1

$56x+72y=40$
$7x+9y=5$
Select the term with the smaller of the two coëfficients and isolate it on the LHS.
$7x=5-9y$
$\text{[1] }x=\frac{5-9y}7=1-y+\frac{-2-2y}7$
$\text{New variable }a=\frac{-2-2y}7$
$-2-2y=7a$
$-2-7a=2y$
$\text{[2] }y=-\frac{2+7a}2=-1-4a+\frac{a}2$
$\text{New variable }b=\frac{a}2$
$a=2b$
Substitute $a\text{ into [2].}$
$y=-\frac{2+7(2b)}2=-\frac{2+14b}2=-1-7b$
Substitute $y\text{ into [1].}$
$x=\frac{5-9(-1-7b)}7=\frac{5+9+63b}7=\frac{14+63b}7=2+9b$
$\text{So, }(x,y)=(2+9b,-1-7b).$
There is an infinitude of integer answers; but your textbook, for some reason, favors $b=2.$

Answer 2

write the equation as $$56x\equiv 40\mod 72$$ or $$x\equiv \frac{40}{76}=\frac{5}{7}\equiv \frac{77}{7}\equiv 11 \mod 72$$ thus $$x=11+72K$$ with $$k \in \mathbb{Z}$$

Answer 3

You can solve $56x+72y=40$ using convergent.

Note: If $\alpha,\beta$ are integral solutions to $ax+by=c$ for $x,y$ respectively, the other solutions take the form$$x=\alpha-bt\\ y=\beta+at\tag{1}$$

---

Here, $a=56,b=72$ so the $x$ values model the form $\alpha-72t$ and $\beta+56t$ for $y$.

The nearest converging fraction to $\dfrac {9}{7}$ is $\dfrac 43$ and hence, we have$$7\cdot 4-3\cdot 9=1$$

For which we can multiply both sides by $40$ to get$$40\cdot 7\cdot 4-3\cdot 9\cdot 40=40\implies 56\cdot 20+72(-15)=40\tag2$$ Thus, we have $\alpha=20,\beta=-15$. And by $(1)$, we get$$x=20-72t\\y=-15+56t$$

Note that we also get the solutions that the book says along the way!