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