Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

2 Answers 2

up vote 13 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|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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.