# 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

The Euclidean algorithm gives: $$85/(1+13i)=1/2-13i/2\approx -6i, \ 85=(-6i)(1+13i)+(7+6i),$$ $$(1+13i)/(7+6i)=1+i, \ 1+13i=(1+i)(7+6i),$$

Hence the gcd is $$7+6i$$.

When going through the Euclidean algorithm, you divide and take a nearest (Gaussian) integer, as 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
• Shouldn't it be $7+6i$ in first line ? – mathemather Jan 30 '19 at 7: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$$, such that $$x = y+z$$ (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.