Sunday, March 13, 2016

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


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...