[issue22477] GCD in Fractions

[gladman]

gladman added the comment:

On 25/09/2014 15:55, Matthew Barnett wrote:
> 
> Matthew Barnett added the comment:
> 
> After some thought, I've come to the conclusion that the GCD of two integers should be negative only if both of those integers are negative.  The basic algorithm is that you find all of the prime factors of the integers and then return the product of the common subset (multiset, actually).
> 
> For example, to calculate the GCD of 6 and 15:
> 
> 6 => [2, 3]
> 15 => [3, 5]
> The largest common subset is [3].
> Therefore the GCD is 3.
> 
> What about negative integers?
> 
> Well, what you could do is make one of the factors -1.
> 
> For example, to calculate the GCD of -6 and 15:
> 
> -6 => [-1, 2, 3]
> 15 => [3, 5]
> The largest common subset is [3].
> Therefore the GCD is 3.
> 
> Another example, to calculate the GCD of -6 and -15:
> 
> -6 => [-1, 2, 3]
> -15 => [-1, 3, 5]
> The largest common subset is [-1, 3].
> Therefore the GCD is -3.

But should the computation of the GCD of two integers by finding the
intersection of their prime factors include -1 or 1 given that neither
of these is a prime?  :-)

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue22477>
_______________________________________