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?

  • $\begingroup$ This may help. $\endgroup$ – projectilemotion Mar 8 '17 at 22:05
  • $\begingroup$ 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$ $\endgroup$ – 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$.


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.