Diophantine equation with negative value

2,012

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$.

Share:
2,012

Related videos on Youtube

Alexis
Author by

Alexis

Updated on February 28, 2022

Comments

  • Alexis
    Alexis over 1 year

    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?

    • projectilemotion
      projectilemotion over 6 years
      This may help.
    • Old Peter
      Old Peter over 6 years
      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$