# Extended Euclidean algorithm with negative numbers

I feel very sorry for asking probably simple and stupid questions on such a site, but a reasonable justification may be that smart answers to stupid questions will vaporize stupidity in the end and help programmers write useful and correct things. :-)

The question is as follows: 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$?

-
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. – Zev Chonoles May 8 '11 at 9:54

## 2 Answers

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

-
Truly! You've answered on the same time I've finally got it myself :-) I accept it, thank you! – wh1t3cat1k May 8 '11 at 9:56

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

-