12
$\begingroup$

Does the Extended Euclidean Algorithm work for negative numbers? If I strip out the sign perhaps it will return the correct GCD, but what exactly to do if I also want $ax + by = GCD(|a|,|b|)$ to be correct (I guess it won't hold anymore as soon as I've stripped out the signs of $a$ and $b$)?

== UPDATE ==

It couldn't be that simple.

If $a$ was negative, then after stripping out signs EEA returns such $x$ and $y$ that $(-a)*x + b*y = GCD(|a|,|b|)$. In this case $a*(-x) + b*y = GCD(|a|,|b|)$ also holds.

The same for $b$.

If both $a$ and $b$ were negative, then $(-a)*x + (-b)*y = GCD(|a|,|b|)$ holds and, well $a*(-x) + b*(-y) = GCD(|a|,|b|)$ ought to hold.

Am I right? Should I just negate $x$ if I have negated $a$ and negate $y$ if I have negated $b$?

  • 5
    Also, don't feel sorry! We have all been confused about something before. This site is for any kind and any level of math question.2011-05-08

2 Answers 2

20

Well, if you strip the sign of $a$ and $b$, and instead run the Euclidean algorithm for $|a|$ and $|b|$, then if your result is $|a|x+|b|y=1$, you can still get a solution of what you want because $a(\text{sign}(a)\cdot x)+b(\text{sign}(b)\cdot y)=1.$

  • 0
    Truly! You've answered on the same time I've finally got it myself :-) I accept it, thank you!2011-05-08
5

You can just change the signs of $x$ and $y$ appropriately.