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 -- https://mail.python.org/mailman/listinfo/python-list