Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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

3 Answers 3

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.

share|improve this answer
+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]$.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.