GCD in Fractions

[random832 at fastmail.us]

On Wed, Sep 24, 2014, at 10:26, Ian Kelly wrote:
> This depends entirely on your implementation of the modulo operation,
> which is an issue of computing since the operator is not used in
> mathematics.

Wikipedia suggests that "remainders from Euclidean division" should be
used. In Euclidean division, the remainder is always positive. (whereas
either C or Python allows the modulo to be negative, in different
situations: in python [round quotient down] the modulo has the same sign
as b, whereas in C [round quotient to zero] the modulo has the same sign
as a).

def mod(a, b):
   r = a % b
   return r + abs(b) if r < 0 else r

def gcd(a, b):
    if b == 0: return a
    else: return gcd(b, mod(a, b))

This appears to give a negative result when:
  a < 0 and b == 0, obviously. A is returned as the gcd.
  a == 0 and b < 0. B is returned as the gcd
  |a| is exactly divisible by |b| and b < 0. B is returned as the gcd.

However, it still lacks the symmetry of gcd(a, b) == gcd(b, a) in some
cases. For example, gcd(-2, 6) is 2, whereas gcd(6, -2) is -2.