# GCD computations in $\mathbb{Z}[i]$

Problem statement:

Find a generator of the ideal $(85, 1+13i)$ in $\mathbb{Z}[i]$, i.e., a GCD for $85$ and $1 + 13i$ by the Euclidean Algorithm. Do the same for the ideal $(47-13i, 53+56i).$

Can you please outline the steps, then I can practice with others.

Source: Abstract Algebra by Dummit & Foote, $\S$8.1 #7

-
Euclid algorithm en.wikipedia.org/wiki/Euclidean_algorithm - your remainders should have the minimal absolute value – user8268 Apr 10 '11 at 21:06
Since $85 = 5\times 17 = (1+2i)(1-2i)(1+4i)(1-4i)$ and $(1+13i)(1-13i) = 170 = 2\times 5\times 17 = (1+i)(1-i)(1+2i)(1-2i)(1+4i)(1-4i)$, it is now easy to check that $1+13i = -i(1+i)(1+2i)(1+4i)$, so that $\gcd(85,1+13i)=(1+2i)(1+4i) = -7+6i$. – Arturo Magidin Apr 10 '11 at 21:42
I resurrected this question (by editing it), since I came across the problem in an algebra book. – The Chaz 2.0 Nov 11 '11 at 14:36
It's also worth pointing out (although not worth posting as an official answer) that since $\mathbb{Z}[i]$ is a UFD, you can compute the $gcd$ of any two nonzero nonunit elements by looking at the prime factorizations in $\mathbb{Z}[i]$ (by, eg, using the norm). Of course, this is computationally much more difficult than simply applying the Euclidean algorithm. – user5137 Nov 11 '11 at 15:44

using the euclidean algorithm $$85/(1+13i)=1/2-13i/2\approx -6i, \ 85=(-6i)(1+13i)+(7-6i)$$ $$(1+13i)/(7-6i)=1+i, \ 1+13i=(7+6i)(-1+i)+0 \text{ no remainder}$$

so the gcd is $7-6i$.

when going through the euclidean algorithm, you just divide and take the nearest (gaussian) integer, just like you would over the (rational) integers.

-
+1, albeit with a slight nitpick: in this context, a "nearest gaussian integer" need not be unique. For any $m,n\in \mathbb{Z}$, $\frac{2m+1}{2} + \frac{2n+1}{2}i\in \mathbb{Q}[i]$ is equidistant to each of $n+mi$, $n+1+mi$, $n+(m+1)i$, and $(n+1)+(m+1)i$. – user5137 Nov 11 '11 at 15:40

A good way to understand the Euclidean algorithm for $\mathbb{Z}[i]$ is to prove that $R:=\mathbb{Z}[i]$ is a Euclidean domain with respect to the function $\varphi(a+bi)=a^2+b^2$. This can be done in the following way:

1) for $x\in\mathbb{Q}$ there are $y\in \mathbb{Z}$ and $z\in\mathbb{Q}$, $|z|\leq \frac 1 2$ (use the Gauss floor function)

2) if $a,b \in R$, then $\frac a b \in \mathbb{Q}(i)$. Write $\frac a b = y_1+z_1 + (y_2+z_2)i$, according to (1), with $y_j \in \mathbb{Z}$ and $z_j \in \mathbb{Q}, ~ |z_j|\leq \frac 1 2$.

3) Now we can write $a=qb+r$, $q:=y_1+y_2i$, $r:=b(z_1+z_2i)$. $q,r \in R$.

4) The important part is: $\varphi(r)<\varphi(b)$ (use the fact that $\varphi$ is multiplicative).

$\varphi$ works just like the absolute value in $\mathbb{Z}$. It will become smaller in every step, so the algorithm will terminate.

From this proof we gather the following algorithm: Compute the fraction $\frac{a}{b}=x+yi$ in $\mathbb{C}$. For $x,y$ choose the closest integers $\tilde x, \tilde y$. Then $a=b(\tilde x + \tilde y i) - r$ with a suitable $r$. In this way you can do a division with remainder in $\mathbb{Z}[i]$.

-

Compute $\rm\ gcd(53+56\ i,\ 47-13\ i)\$ by using a (Euclidean) remainder sequence, e.g.

$\rm(1)\quad\quad\quad\quad 56\ i +53$

$\rm(2)\quad\quad\ -13\ i + 47$

$\rm(3)\quad\quad\quad\quad\ \ 9\ i + 40\quad\quad$ by $\rm\ \ \ \ \ \ (1) - \:i\ (2)$

$\rm(4)\quad\quad\quad\quad\ \ 7\ i + 22\quad\quad$ by $\rm\ \ \ \ i \ (2) - \:i\ (3)$

$\rm(5)\quad\quad\quad\quad\quad 5\ i + 4\ \quad\quad$ by $\rm\ - (3) + 2\ (4)\:,\$

Note $\rm\ p\: =\: \ 5\ i + 4\$ is prime, since it has prime norm $= 41\:.\:$ Hence the gcd will be either $\rm\:p\:$ or $1\:,\:$ depending on if $\rm\:p\:$ divides $\rm\:q = 7\ i + 22\:;\$ it does: $\rm\:p\:p' = 41\:$ divides $\rm\ q\:p' = 123 - 82\ i\:.$

The first problem is much simpler, involving only two divisions - see yoyo's answer.

-