Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 14 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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