2
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ The title should be the gcd of Gaussian Integers. $\endgroup$ – Michael Burr Mar 24 '15 at 11:18
  • $\begingroup$ @MichaelBurr, Thanks $\endgroup$ – Richard Mar 24 '15 at 11:21
  • $\begingroup$ Frankly, what you wrote is almost unintelligible... $\endgroup$ – A.P. Mar 24 '15 at 11:30
  • $\begingroup$ @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. $\endgroup$ – Richard Mar 24 '15 at 11:33
  • $\begingroup$ Do you know what is the norm of an element in $\Bbb{Z}[i]$? $\endgroup$ – A.P. Mar 24 '15 at 11:33
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ So, if any $a$, $b$ in $\mathbb{Z}[i]$, $(N(a),N(b)) \neq 1$ implies a, b are not relatively prime? $\endgroup$ – Richard Mar 24 '15 at 11:50
  • $\begingroup$ 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]$ ? $\endgroup$ – Richard Mar 24 '15 at 11:54
  • $\begingroup$ 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. $\endgroup$ – A.P. Mar 24 '15 at 11:55
  • $\begingroup$ It may be, but not like you wrote: $5.8 + 0.6i$ is not an element in $\Bbb{Z}[i]$! $\endgroup$ – A.P. Mar 24 '15 at 11:55
  • $\begingroup$ 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] $ ? $\endgroup$ – Richard Mar 24 '15 at 11:59
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ @A.P. Please tell me what part you do not understand so I can elaborate. $\endgroup$ – Bill Dubuque Mar 25 '15 at 13:21
  • $\begingroup$ 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}$)? $\endgroup$ – A.P. Mar 25 '15 at 13:32
  • $\begingroup$ $\,\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? $\ \ $ $\endgroup$ – Bill Dubuque Mar 25 '15 at 14:03
  • $\begingroup$ Yes. That's what I said in my comment, although in different terms. ;) $\endgroup$ – A.P. Mar 25 '15 at 14:15
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Mar 25 '15 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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