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.

  • 1
    $\begingroup$ Remember that $20=5 \times 4$ and $-15=5 \times 3$. Both answers are correct $\endgroup$
    – user284001
    Nov 15, 2016 at 16:49
  • $\begingroup$ @Bacon, So why did they multiply by 5? $\endgroup$
    – monalisa
    Nov 15, 2016 at 16:50
  • $\begingroup$ At the outset you noted that $8|40$ and this is... $\endgroup$
    – user284001
    Nov 15, 2016 at 16:50

3 Answers 3


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


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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.