# Diophantine equation with negative value

Find the general solution to 10x -8y = 42

Okay, so do I find gcd(10, -8)? (this is clearly 2 but I need to use euclid's algorithm so I can work backwards to find the general solution)

If I do that I get

10 = -8(1) + 18 -8 = 18(1) - 26 18 = -26(1) + 44 -26 = 44

so this isn't going to work as every line gets further away rather than closer to a solution.

Should I just find gcd(10, 8)

10 = 8(1) + 2 8 = 4(2) + 0 gcd = 2 But then how do I accommodate for it being a negtive y?

• This may help. – projectilemotion Mar 8 '17 at 22:05
• IMHO, always start by reducing a linear equation to its simplest form, by dividing through by any common factor. In this case $5x-4y=21$ – Old Peter Mar 9 '17 at 14:13

It's easiest if you just start with $10$ and $8$ then be careful with the signs when you are working out $x$ and $y$.
However it is also possible to work with negative numbers as long as you make sure the reminder when dividing by $b$ is always from $0$ to $|b|-1$. (So your first step with remainder $18$ was wrong.) For $10$ and $-8$ the Euclidean algorithm would be \eqalign{ 10&=(-1)(-8)+2\cr -8&=(-4)(2)\cr} and since the remainder is zero, that's it. Working backwards you have $$2=10(1)-(-8)(-1)$$ which is $$2=10(1)-8(1)\ .$$ Multiplying by $21$ gives $$42=10(21)-8(21)$$ and comparing with $10x-8y=42$ gives a possible solution $x=21$, $y=21$.