使用 SymPy 查找高斯整数中的最大公约数 (GCD)

Question

我尝试使用 Sympy 求出两个高斯整数的 GCD，但无法得到正确的结果。例如，函数

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

应该return2+I（I是虚数单位）因为(2+I)*(2-I)=5是高斯整数。然而它 returns 1。

Answer 1

看起来 gcd 对高斯整数的了解不够（即，一个错误）。不过，您可以根据欧几里德算法使用自己的函数。

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)

测试：

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

检查最后一项：30 = (4+2*I)*(6-3*I) 和 18+4*I = (4+2*I)*(4-I)。

使用 SymPy 查找高斯整数中的最大公约数 (GCD)

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

python

sympy

greatest-common-divisor