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
    $\begingroup$ 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. $\endgroup$ – 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.$$

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.