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