GCD in Fractions

[Steven D'Aprano]

blindanagram wrote:

> What is the rationale for gcd(x, y) in Fractions returning a negative
> value when y is negtive?

Good question.

Normally, gcd is only defined for non-negative integers. Wolfram Mathworld,
for example, doesn't mention negative values at all (as far as I can see):

http://mathworld.wolfram.com/GreatestCommonDivisor.html

although buried deep in the documentation for Mathematica's GCD function is
hidden the fact that it treats GCD(-a, -b) the same as GCD(a, b):

http://functions.wolfram.com/IntegerFunctions/GCD/04/02/01/

and sure enough Wolfram Alpha tells me that the GCD of *all* of:

(100, 20)
(-100, 20)
(100, -20)
(-100, -20)

are equal to +20. On the other hand, Excel and LibreOffice both give an
error for the GCD of a negative value, and I've seen versions of gcd()
which do the same as fractions.gcd. So I think there is not one single
standard way to extend GCD to negative numbers.

> For example gcd(3, -7) returns -1, which means that a co-prime test that
> would work in many other languages 'if gcd(x, y) == 1' will fail in
> Python for negative y.

True, but either of:

abs(gcd(x, y)) == 1
gcd(x, y) in (1, -1)

will work.


> And, of course, since -|x| is less than |x|, returning -|x| rather than
> |x| is not returning the greatest common divisor of x and y when y is
> negative.

That's a good argument for gcd if it were in a general maths module, but
since it is specifically used for generating fractions, I guess that the
developers won't be very convinced by that.




-- 
Steven