Compute xgcd over Gaussian integers

asked 2019-02-13 10:25:35 +0200

Hilder Vitor Lima Pereira gravatar image

updated 2019-02-13 10:26:39 +0200

As you can see below, I can create the ring of Gaussian integers and compute the greatest common divisor of two elements:

sage: ZZ[I]
Gaussian Integers in Number Field in I with defining polynomial x^2 + 1
sage: F = ZZ[I].random_element()
sage: G = ZZ[I].random_element()
sage: F
-I - 4
sage: G
-I + 1
sage: gcd(F, G)

However, when I try to find $u, v \in \mathbf{Z}[i]$ such that $u\cdot F + v\cdot G = 1$ in $\mathbf{Z}[i]$ (that is, to run the extended GCD), I get the following error:

sage: xgcd(F, G)

. . .

TypeError: Unable to coerce -I - 4 to an integer

Do you know how I can find such $u$ and $v$?

edit retag flag offensive close merge delete



I don't think this is built in yet, but see this question for an implementation: Solving systems of congruences with Gaussian integers (the extended_euclides with gaussian_quo).

rburing gravatar imagerburing ( 2019-02-13 13:11:26 +0200 )edit

@rburing I see. Thank you very for the comment. It was very useful!

Hilder Vitor Lima Pereira gravatar imageHilder Vitor Lima Pereira ( 2019-02-13 16:38:18 +0200 )edit