This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author mark.dickinson
Recipients, gladman, mark.dickinson, vstinner
Date 2014-09-24.09:13:40
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
> I will willingly supply more references if you need them.

I don't. :-) I've taught more elementary number classes and reviewed more elementary number theory texts (including Rosen's) than I care to remember, and I have plenty of my own references. I stand by my assertion that the fractions module gcd is not wrong:  it returns 'a' greatest common divisor for arbitrary integer inputs.

A bit more: the concept of greatest common divisor is slightly ambiguous:  you can define the notion of "a greatest common divisor" for an arbitrary commutative ring-with-a-1 R:  c is a greatest common divisor of a and b if c is a common divisor (i.e. c divides a and c divides b, where "x divides y" is synonymous with "y is a multiple of x"), and any other common divisor divides c.  No ordering is necessary: "greatest" here is with respect to the divisibility lattice rather than with respect to any kind of total ordering.  One advantage of this definition is that it makes it clear that 0 is a greatest common divisor of 0 and 0.

If further R is an integral domain, then it follows immediately from the definition that any two greatest common divisors of a and b (if they exist) are associates: a is a unit times b.  In the particular case where R is the usual ring of rational integers, that means that "the" greatest common divisor of two numbers a and b is only really defined up to +/-;  that is, the sign of the result is unimportant.  (An alternative viewpoint is to think of the gcd, when it exists, as a principal ideal rather than an element of the ring.)

See for more along these lines.

So you're using one definition, I'm using another.  Like I said, there's no universal agreement. ;-).
Date User Action Args
2014-09-24 09:13:41mark.dickinsonsetrecipients: + mark.dickinson, vstinner, gladman,
2014-09-24 09:13:41mark.dickinsonsetmessageid: <>
2014-09-24 09:13:41mark.dickinsonlinkissue22477 messages
2014-09-24 09:13:40mark.dickinsoncreate