GCD in Fractions

[Ian Kelly]

On Wed, Sep 24, 2014 at 5:44 AM, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> 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.

Well, this definition would imply that gcd(a, b) should always return
*two* results, one positive and one negative. I don't think anybody
wants that. It would make more sense to standardize on one of them,
and if we take sqrt as an example, then the result should be positive.

> 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

This depends entirely on your implementation of the modulo operation,
which is an issue of computing since the operator is not used in
mathematics.  The algorithm itself only specifies at each step to
solve the equation R_{n-2} = Q * R_{n-1} + R_{n}, such that |R_{n}| <
|R_{n-1}|. For any given input there can be many possible solutions,
both positive and negative, regardless of the signs of the inputs, and
it doesn't matter which solution you choose. So one could implement
Euclid's algorithm to return either a positive or negative result for
any arbitrary pair of integers.