Extended Euclidean algorithm with negative numbers

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

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.$$
You can just change the signs of $x$ and $y$ appropriately.