GCD in Fractions

Johann Hibschman jhibschman at gmail.com
Wed Sep 24 20:09:12 CEST 2014


Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:

> blindanagram wrote:
>
>> Seccondly (as others here have pointed out), the mathematical properties
>> of the greatest common divisor are well defined for both positive and
>> negative integers.
>
> You keep saying that, but it simply is not true. Different people use
> different definitions. Some refuse to allow negative arguments at all. Some
> insist that the GCD must be positive. Others allow it to be negative.

I can't find a good source for allowing it to be negative, though.
Clearly, the primary use of the function is on the positive integers,
with the negatives being an extension.

> Mathworld does show one thing that suggests an interpretation for the GCD of
> negative values:
>
>  The GCD is distributive
>     GCD(ma,mb)=mGCD(a,b) 
>
> which tells us that:
>
>     GCD(-x, -y) = -GCD(x, y)
>
> And yet, Mathematica has:
>
>     GCD(-x, -y) = GCD(x, y)
>
> the very opposite of what Mathworld says, despite coming from the same
> people.

This is most likely simply them dropping the constraint that m must be
non-negative.  Wikipedia, for example, specifies it under "Properties."

> The Collins Dictionary of Mathematics (second edition, 2002) says:
>
>     highest common factor, greatest common factor, or greatest 
>     common divisor (abbrev hcf, gcf, gcd)
>
>     n, an integer d that exactly divides (sense 2) two given 
>     integers a and b, and is such that if c divides a and b, 
>     then c divides d; this definition extends to finite sets 
>     of integers and to integral domains. For example, the 
>     highest common factor of 12, 60 and 84 is 12.
>
> Yet again, we have no clear definition for negative values.

As pointed out, this definition always yields two values (positive and
negative), even for positive a and b, so there's nothing special for
negative a or b.  Typically, I've seen this augmented with "choose the
positive one" to get a single value.

> Here's an example using Euclid's algorithm to calculate the GCD of negative
> numbers, and sure enough, you get a negative result:

The algorithm is pretty irrelevant here.  gcd's not defined by a
particular algorithm to calculate it.

>From everything that I've seen, mathematicians consider the gcd to be
always positive.

Now, that's not saying that fraction should implement the mathematical
gcd, if it doesn't need it.  That should be its own argument, though;
it doesn't help to add false doubt about what the gcd of negative
numbers should be.

Cheers,
Johann



More information about the Python-list mailing list