JuliaLang/julia — pull request #4811 by stevengj (2013-11-14 18:38:45+00:00)
Title: fix gcd & lcm sign and optimize gcdx and invmod

The attached patch fixes several bugs (#4810):

* gcd, lcm, and gcdx, returned inconsistent signs between BigInt and other integer types. Now they always return a positive gcd and lcm.
* invmod was broken for negative arguments, since it was incorrectly interpreting a gcd of `-1` as meaning that the inverse did not exist.
* `Rational` construction was broken for BigInt because of the gcd sign inconsistency.

I also rewrote `gcdx` non-recursively to make it about 20x faster on my machine, and use the GMP `invmod` function directly for `BigInt`.