Find the Greatest Common Divisor (GCD) in Gaussian Integers with SymPy

Question

I try to find the GCD of two gaussian integers using Sympy but couldn't get the correct result. For example, the function

gcd(2+I,5, gaussian = True)

should return 2+I(I is the imaginary unit) because (2+I)*(2-I)=5 in gaussian integers. However it returns 1.

Answer 1

Looks like gcd is insufficiently aware of Gaussian integers (i.e., a bug). You can use your own function, though, based on the Euclidean algorithm.

from sympy import sympify, I, expand_mul
def my_gcd(a, b):
    a, b = map(sympify, (a, b))
    if abs(a) < abs(b):
        a, b = b, a
    cr, ci = (a/b).as_real_imag()
    if cr.is_integer and ci.is_integer:
        return -b if b.could_extract_minus_sign() else b
    c = int(round(cr)) + I*int(round(ci))
    return my_gcd(a - expand_mul(b*c), b)

Testing:

my_gcd(30, 18)   #  6
my_gcd(5, 2+I)   #  2+I
my_gcd(30, 18+4*I)   # 4 + 2*I

Checking the last of these: 30 = (4+2*I)*(6-3*I) and 18+4*I = (4+2*I)*(4-I).