GCD in Fractions

Steven D'Aprano steve+comp.lang.python at pearwood.info
Wed Sep 24 13:44:10 CEST 2014


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.

GCD is well-defined for **positive integers only**.

Mathworld emphasises "positive integers" in their definition, repeating the
phrase THREE times in the first paragraph:

    The greatest common divisor, sometimes also called the highest 
    common divisor (Hardy and Wright 1979, p. 20), of two positive 
    integers a and b is the largest divisor common to a and b. For 
    example, GCD(3,5)=1, GCD(12,60)=12, and GCD(12,90)=6. The 
    greatest common divisor GCD(a,b,c,...) can also be defined for 
    three or more positive integers as the largest divisor shared 
    by all of them. Two or more positive integers that have greatest
    common divisor 1 are said to be relatively prime to one another,
    often simply just referred to as being "relatively prime." 

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

The rest of the page avoids mentioning anything about negative values. There
are five graphs on the page, all five are limited to only positive values.

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.

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


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.

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

https://answers.yahoo.com/question/index?qid=20111021023909AA8bCjB

Wikipedia, on the other hand, defines GCD:

    In mathematics, the greatest common divisor (gcd), also 
    known as the greatest common factor (gcf), highest common 
    factor (hcf), or greatest common measure (gcm), of two or 
    more integers (when at least one of them is not zero), is 
    the largest positive integer that divides the numbers 
    without a remainder.

https://en.wikipedia.org/wiki/Greatest_common_divisor


So:

- Mathworld says that GCD of two negative numbers is a negative number;

- but Mathematica says that GCD of two negative numbers is a positive;

- Wikipedia agrees with Mathematica and disagrees with Mathworld;

- Euclid's algorithm returns negative values for the GCD of two negatives;

- Collins Dictionary gives a definition which is met by either positive
  or negative results.




-- 
Steven




More information about the Python-list mailing list