# Find the gcd of Gaussian Integers

Find the greatest common divisor in $\mathbb{Z}[i]$ of $11+7i$ and $18-i$.

Actually, I don't know why I have to calculate $b\bar{a}=191-137i$, and $a\bar{a}=170$,

and this $191-137i = 170(?)+(21+33i), ?=1-i$.

Then, I can get $18-i=(11+7i)(1-i)+3i$.

Following $11+7i=(3i)(2-3i)+2+i$, $3i=(2+i)(1+i)-1$, $(2+i)=(-1)(-2-i)$

I get (2+i) is the g.c.d. (Is it really right?)

• The title should be the gcd of Gaussian Integers. – Michael Burr Mar 24 '15 at 11:18
• @MichaelBurr, Thanks – Richard Mar 24 '15 at 11:21
• Frankly, what you wrote is almost unintelligible... – A.P. Mar 24 '15 at 11:30
• @A.P., I was trying to figure out the g.c.d.. But I don't know the reason behind for the steps I knew. – Richard Mar 24 '15 at 11:33
• Do you know what is the norm of an element in $\Bbb{Z}[i]$? – A.P. Mar 24 '15 at 11:33

Recall that if $N(a+ib) = a^2+b^2$ and $d,x \in \Bbb{Z}[i]$, then $d \mid x$ implies $N(d) \mid N(x)$. Now, an easy computation shows that \begin{align} N(11 + 7i) &= 170 = 2 \cdot 5 \cdot 17 \\ N(18 - i) &= 325 = 5^2 \cdot 13 \end{align} hence $d = \gcd(11 + 7i,18 - i)$ is either an element of norm $5$ or a unit, because it can be proved that $N(u) = 1$ iff $u$ is invertible. Now, the only solutions in $\Bbb{Z}^2$ of $$a^2 + b^2 = 5$$ are $(\pm 1, \pm 2)$ and $(\pm 2, \pm 1)$, so the only elements of norm $5$ in $\Bbb{Z}[i]$ are $\pm 1 \pm 2i$ and $\pm 2 \pm i$. Since the $d$ is unique up to multiplication by a unit, it is enough to check if any of these divides both $11 + 7i$ and $18 - i$.

Note that the only solutions in $\Bbb{Z}[i]$ of $$N(a + bi) = a^2 + b^2 = 1$$ are $\pm 1, \pm i$, so these are the only units. In particular, this means that it is enough to check if $$d = 1 + 2i \quad \text{or} \quad d = 1 - 2i$$ because these are not associated and every element of norm $5$ is associated to one of these (note that $2 + i = i(1 - 2i))$. Further, we can observe that only one of these can divide, say, $11 + 7i$, because otherwise $(1 + 2i)(1 - 2i) = 1 + 4 = 5$ would divide it, too (and this is absurd). The same holds for $18 - i$.

Finally, observe that $$(1 + 2i)(a + bi) = a - 2b + (2a + b)i$$ hence $(1 + 2i) \mid x + yi$ in $\Bbb{Z}[i]$ if and only if there are $a,b \in \Bbb{Z}$ such that $$\begin{cases} x = a - 2b \\ y = 2a + b \end{cases}$$ This system gives $(1 + 2i)(5 - 3i) = 11 + 7i$ (so, in particular, your solution is wrong), but it has no solution for $18 - i$. Indeed $$\begin{cases} 18 = a - 2b \\ -1 = 2a + b \end{cases} \quad \leftrightarrow \quad \begin{cases} 2b = a - 18 \\ -2 = 4a + 2b \end{cases} \quad \leftrightarrow \quad \begin{cases} 2b = a - 18 \\ 5a = 16 \end{cases}$$ has no solutions in $\Bbb{Z}^2$. Therefore $\gcd(11 + 7i,18 - i) = 1$.

• So, if any $a$, $b$ in $\mathbb{Z}[i]$, $(N(a),N(b)) \neq 1$ implies a, b are not relatively prime? – Richard Mar 24 '15 at 11:50
• I want to know, suppose $2+i$ is g.c.d. then, $(11+7i)=(2+i)(5.8+0.6i)$. Is $(2+i)$ a factor of $(11+7i)$ in $\mathbb{Z}[i]$ ? – Richard Mar 24 '15 at 11:54
• I'm saying that if $(a,b) = d$, then $(N(a),N(b)) = N(d)$, which allows you to restrict the possible choices for $d$. Right now I'm not sure about the converse implication, but I don't think that it is true. – A.P. Mar 24 '15 at 11:55
• It may be, but not like you wrote: $5.8 + 0.6i$ is not an element in $\Bbb{Z}[i]$! – A.P. Mar 24 '15 at 11:55
• but $(11+7i)=(2+i)(5.8+0.6i)$ right? So, if $(2+i)$ is the g.c.d. but $(2+i) \nmid (11+7i) in \mathbb{Z}[i]$ ? – Richard Mar 24 '15 at 11:59

Let $\,x = 11\!+\!7i,\,y = 18\!-\!i.\,$ Then $\,d\mid x,y\,\Rightarrow\,d\mid \overbrace{x\bar x}^{170},\overbrace{y\bar y}^{325}\,\Rightarrow\,d\mid(170,325)=5$

But neither prime factor of $\,5 = (2\!-\!i)(2\!+\!i)\,$ divides both $\,x,y\,$ since by the Lemma

\qquad \ \begin{align}5&\,\nmid\ 18 - 1(2)\\ \Rightarrow\ i\!-\!2&\,\nmid\, 18 - 1\,(i)\end{align}\qquad and \qquad\, \begin{align}5&\,\nmid\, 11 + 7(-2)\\ \Rightarrow\ i\!+\!2&\,\nmid\, 11 + 7\,( i)\end{align}

Lemma $\ i\!-\!2\mid a\!+\!bi \iff 5\mid a\!+\!b(2)\,\$ and $\,\ i\!+\!2\mid a\!+\!bi\iff 5\mid a\!+\!b(-2),\$ because

$\ {\rm mod}\,\ \color{}{i\!-\!2}\!:\ \color{#c00}{i\equiv 2}\,\Rightarrow\, a\!+\!b\,\color{#c00}i\equiv a\!+\!b(\color{#c00}2),\$ and $\ i\!-\!2\mid n\iff 5\mid n(i\!+\!2)\iff 5\mid n$

Remark $\$ Generally we can use module normal forms (Hermite) to test ideal membership. By this Lemma we know that the ideal $\,(i\!-\!2) = (5,i\!-\!2) = 5\,\Bbb Z + (i\!-\!2)\Bbb Z\,$ by $\,5\mid N(i\!-\!2),\ N =$ norm. Just as in linear algebra, it is easy to test membership when the subspace basis is triangularized. Here it amounts to modding out first by $\,i\!-\!2\,$ (i.e. replacing $\,i\,$ by $2)\,$ then modding out by $\,5.$

Alternatively we can use the Euclidean algorithm.

Note $\ d\mid 18\!-\!i,11\!+\!7i\,\Rightarrow\, d\mid 18\!-\!i-(11\!+\!7i) = 7\!-\!8i,$

thus $\ d\mid 11\!+\!7i-i(7\!-\!8i) = 3\,\Rightarrow\, d\mid 3(6)-(18\!-\!i) = i\,\Rightarrow d\mid i(-i) = 1$

Remark $\$ Unwinding gives Bezout $\ (6-6i)(11+7i) + (i-6)(18-i) = 1$

• @A.P. Please tell me what part you do not understand so I can elaborate. – Bill Dubuque Mar 25 '15 at 13:21
• Maybe I understand now. Do you mean that the class of $a+bi$ modulo $i-2$ is the same as the class of $a+2b$ and that $i-2$ divides an integer $n$ iff its norm does (which is clear, because $i-2 \mid n$ means $n \in (i-2)\Bbb{Z}[i] \cap \Bbb{Z}$)? – A.P. Mar 25 '15 at 13:32
• $\,\color{#c00}{i\!-\!2}\mid a\!+\!bi = a\!+\!b(2\!-\!2\!+\!i) = a\!+\!b(2)\!+\!b(\color{#c00}{i\!-\!2})\iff i\!-\!2\mid a\!+\!b(2).\,\$ More generally $\,i\!-\!c\mid f(i)\iff i\!-\!c\mid f(c)\$ for any polynomial $\,f\in\Bbb Z[x]\$ by $\ i\equiv c\pmod{i\!-\!c}.\$ $\tag*{}$ If $\,n\in\Bbb Z\,$ then by rationalizing the denominator $$\dfrac{n}{2-i}\, =\, \dfrac{n}{2-i}\,\dfrac{2+i}{2+i}\, =\, \dfrac{2n}5 + \dfrac{n}5\, i\,\in\, \Bbb Z[i]\iff 5\mid n$$ @A.P. Clearer now? $\ \$ – Bill Dubuque Mar 25 '15 at 14:03
• Yes. That's what I said in my comment, although in different terms. ;) – A.P. Mar 25 '15 at 14:15
• @A.P. Right, but I thought an unwinding into more elementary terms might help other readers too (and I had already started writing it before your comment appeared). – Bill Dubuque Mar 25 '15 at 14:17