ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 13 Feb 2019 16:38:18 +0100Compute xgcd over Gaussian integershttps://ask.sagemath.org/question/45441/compute-xgcd-over-gaussian-integers/As you can see below, I can create the ring of [Gaussian integers](https://en.wikipedia.org/wiki/Gaussian_integer) 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)
1
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$?Wed, 13 Feb 2019 10:25:35 +0100https://ask.sagemath.org/question/45441/compute-xgcd-over-gaussian-integers/Comment by rburing for <p>As you can see below, I can create the ring of <a href="https://en.wikipedia.org/wiki/Gaussian_integer">Gaussian integers</a> and compute the greatest common divisor of two elements:</p>
<pre><code>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)
1
</code></pre>
<p>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:</p>
<blockquote>
<p>sage: xgcd(F, G)</p>
<p>. . .</p>
<p>TypeError: Unable to coerce -I - 4 to an integer</p>
</blockquote>
<p>Do you know how I can find such $u$ and $v$?</p>
https://ask.sagemath.org/question/45441/compute-xgcd-over-gaussian-integers/?comment=45448#post-id-45448I don't think this is built in yet, but see this question for an implementation: [Solving systems of congruences with Gaussian integers](https://ask.sagemath.org/question/44287/solving-systems-of-congruences-with-gaussian-integers/) (the `extended_euclides` with `gaussian_quo`).Wed, 13 Feb 2019 13:11:26 +0100https://ask.sagemath.org/question/45441/compute-xgcd-over-gaussian-integers/?comment=45448#post-id-45448Comment by Hilder Vitor Lima Pereira for <p>As you can see below, I can create the ring of <a href="https://en.wikipedia.org/wiki/Gaussian_integer">Gaussian integers</a> and compute the greatest common divisor of two elements:</p>
<pre><code>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)
1
</code></pre>
<p>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:</p>
<blockquote>
<p>sage: xgcd(F, G)</p>
<p>. . .</p>
<p>TypeError: Unable to coerce -I - 4 to an integer</p>
</blockquote>
<p>Do you know how I can find such $u$ and $v$?</p>
https://ask.sagemath.org/question/45441/compute-xgcd-over-gaussian-integers/?comment=45451#post-id-45451@rburing I see. Thank you very for the comment. It was very useful!Wed, 13 Feb 2019 16:38:18 +0100https://ask.sagemath.org/question/45441/compute-xgcd-over-gaussian-integers/?comment=45451#post-id-45451