Topics in Algebra, Chapter 3.8

2013-01-28 math algebra topics-in-algebra

---

This page covers section 3.8 (“A Particular Euclidean Ring”).

Topics covered: 3.8

• $\mathbb{Z}[i]$, the Gaussian integers, is the set of complex numbers $a+bi$ where $a,b\in \mathbb{Z}$. The proof of each result in this chapter is very clever.

• Theorem 3.8.1: $\mathbb{Z}[i]$ is a Euclidean ring. The distance function is $d(a+bi)=a^2+b^2$.

• Lemma 3.8.1: Let $c,p\in \mathbb{Z}$ with $p$ prime and $(c,p)=1$ such that there exist $x,y\in \mathbb{Z}$ with $x^2+y^2=cp$. Then there exist integers $a,b\in \mathbb{Z}$ such that $p=a^2+b^2$.

• Lemma 3.8.2: If $p\in \mathbb{Z}$ is a prime of the form $4n+1$, $n$ an integer, then there exists $x\in \mathbb{Z}$ such that $x^2\equiv -1\mathrm{m}\mathrm{o}\mathrm{d}p$.

• Theorem 3.8.2 (Fermat): If $p\in \mathbb{Z}$ is a prime of the form $4n+1$, $n$ an integer, then there exist $a,b\in \mathbb{Z}$ such that $p=a^2+b^2$.

The problems below are paraphrased from/inspired by those given in Topics in Algebra by Herstein. The solutions are my own unless otherwise noted. I will generally try, in my solutions, to stick to the development in the text. This means that problems will not be solved using ideas and theorems presented further on in the book.

Herstein 3.8.1: Find all the units in $\mathbb{Z}[i]$.

Suppose $a+bi\in \mathbb{Z}[i]$ is a unit, so there exists $r+si\in \mathbb{Z}[i]$ with $$1=(a+bi)(r+si)\mathrm{.}$$

We have that $1=d(1)=d(a+bi)d(r+si)$ and $d$ maps into the non-negative integers. This forces the norm of a unit to be $1$. Then we have $d(a+bi)=a^2+b^2=1$, and we easily enumerate the solutions as $\pm 1,\pm i$. These are the four units of $\mathbb{Z}[i]$.

Herstein 3.8.2: Prove that if $a+bi\in \mathbb{Z}[i]$ is non-zero and is not a unit, then $a^2+b^2>1$.

Lemma 3.7.3, states that, in a Euclidean ring, multiplication by a non-zero unit always increases the norm of an element. That is, with $r,s$ elements of Euclidean ring $R$ and $s\mathrm{\ne }0$, we have that $d(r)<d(rs)$. In particular, here we may say that $$1=d(1)<d(1\cdot (a+bi))=a^2+b^2\mathrm{.}$$

Herstein 3.8.3: Find the greatest common divisor in $\mathbb{Z}[i]$ of

(a) $3+4i$ and $4-3i$.

(b) $11+7i$ and $18-i$.

We remark that the greatest common divisor is only unique up to association (multiplication by unit). As proven in problem 3.7.4, the prescription given there will produce greatest common divisors. Still, how does one pick out the quotients $q_i$?

(a) We will try to divide $4-3i$ into $3+4i$. We need to find a quotient that gives us a remainder small enough to be acceptable in the algorithm. That is, we seek $q_0$ such that $3+4i=q_0(4-3i)+r_1$ with $d(r_1)<d(4-3i)=25$. Drawing the two points on the complex plane gives a hint. $4-3i$ can be brought near to $3+4i$ by a rotation of $\pi \mathrm{/}2$ about the origin, which is equivalent to a multiplication by $i$. Then we take $q_0=i$.

But, oops! $i(4-3i)=3+4i$ so we are already done. Their greatest common divisor is $4-3i$ (or $3+4i$, which we have just seen is its associate).

(b) This time we may have a less trivial situation. Again drawing the picture on the complex plane we see that $18-i$ may be brought somewhat near to $11+7i$ if it is rotated by $\pi \mathrm{/}2$, or equivalently, multiplied by $i$. A rotation by something like $\pi \mathrm{/}6$ might be even better, but our choice should be fine. Thus we take $q_0=i$ and write $$11+7i=i(18-i)+10-11i$$

so that $r_1=10-11i$. This is okay because $d(r_1)=221<325=d(18-i)$. Drawing out the points $18-i$ and $10-11i$, we really think a rotation by $\pi \mathrm{/}4$ of $10-11i$ would be helpful in this case. Of course, we can’t multiply by $e^{i\pi \mathrm{/}4}$ because there is nothing like $\sqrt{2}$ in our ring. Taking the next best thing, we will try $q_1=1+i$. Thus, we write $$18-i=(1+i)(10-11i)-3.$$

Then $r_2=-3$ and $d(r_2)=9<221=d(r_1)$, so we have improved considerably.

Now a glance at $10-11i=q_2(-3)+r_3$ suggests $q_2=-3+4i$ and therefore $r_3=1+i$. We have $d(r_3)=2<9=d(r_2)$. Continuing, we can write $$-3=(1+i)(i-1)-1,$$

which puts $q_3=i-1$ and $r_4=-1$. At last, we are done, because $r_3=-(1+i)r_4$. Therefore the greatest common divisor of $11+7i$ and $18-i$ is $-1$, or equivalently $1$: they are relatively prime. We can exhibit two Gaussian integers $x,y$ such that $(11+7i)x+(18-i)y=1$. They may be found by tracing backwards all of the steps of the algorithm, whereupon we find $$r_4=(1+q_0{q}_1+q_0{q}_3+q_2{q}_3+q_0{q}_1{q}_2{q}_3)(18-i)-(q_1+q_3+q_1{q}_2{q}_3)(11+7i)\mathrm{.}$$

Plugging in values, $$(-6+i)\cdot (18-i)+(6-6i)\cdot (11+7i)=1.$$

Herstein 3.8.4: Let $p$ be a prime integer of the form $4k+3$ with $k\in \mathbb{Z}$. Prove that there can not be an $x\in \mathbb{Z}$ with $x^2\equiv -1\mathrm{m}\mathrm{o}\mathrm{d}p$.

Suppose that such an $x$ existed, with $x^2+1=cp$ for some $c\in \mathbb{Z}$. Then we fall into the case of Lemma 3.8.1 which says that $p$ may be expressed as a sum of two squares, $p=a^2+b^2$. Looking at this equation modulo $4$, we find that it has no solutions: $p\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}4$ while squares modulo $4$ can be only $0$ or $1$ so that $a^2+b^2$ can only take the values $\{0,1,2\}$. This contradiction forces us to conclude that no such $x$ may exist.

It is easy to see that the only quadratic residues modulo $4$ are $0$ and $1$. If $k\in \mathbb{Z}$ then $(2k{)}^2=4k^2\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}4$, so even numbers will always square to zero modulo $4$. On the other hand, $(2k+1{)}^2=4k^2+4k+1\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}4$, so odd numbers will always square to $1$ modulo $4$.

Alternate solution: In light of problem 3.8.5, which suggests that my method (invoking Lemma 3.8.1) is too heavy-handed, here is another solution. Fermat’s little theorem says that such an $x$ would have $$x^{p-1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}p,$$

where we have used the fact that $p\mid ̸x$. Now, this may be rewritten as $$x^{4k+2}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}p\mathrm{.}$$

On the other hand, from $x^2\equiv -1\mathrm{m}\mathrm{o}\mathrm{d}p$, we have that $$x^{4k+2}\equiv x^{2(2k+1)}\equiv (-1{)}^{2k+1}\equiv -1\mathrm{m}\mathrm{o}\mathrm{d}p,$$

which is a contradiction. Hence no such $x$ exists.

Herstein 3.8.5: Let $p$ be a prime integer of the form $4k+3$ with $k\in \mathbb{Z}$. Prove that there do not exist $a,b\in \mathbb{Z}$ with $p=a^2+b^2$.

This was proven in the course of solving problem 3.8.4, where we consider the equation $p=a^2+b^2$ modulo $4$.

Herstein 3.8.6: Prove that there are infinitely many primes of the form $4k+3$ with $k\in \mathbb{Z}$.

First let us recall Euclid’s proof that there are infinitely many prime numbers. Suppose to the contrary that there was only a finite set of prime numbers, $\{p_1,\dots ,p_N\}$. Then construct $P=p_1\cdots p_N$ and $Q=P+1$. Because any integer can be factored into primes, we know that $Q$ has some prime divisor $p$. If $p$ were to belong to the supposed set, however, then we would have $p\mid Q$ and $p\mid P$, so that $p\mid (Q-P)=1$ which is not possible. Therefore $Q$ necessarily has a prime divisor which does not belong to our list, so the list is incomplete whenever it is finite. Note that $Q$ itself is not necessarily a prime (though it sometimes is), but rather that its prime divisors are all “new” — none belonged to the old list. For instance, $2\cdot 3\cdots 11\cdot 13+1=59\cdot 509$.

Now we turn to the problem of primes of the form $4k+3$. It is natural to consider things like $$Q=(4k_1+3)\cdots (4k_N+3)\pm 1$$

but quick numerical investigations show that these do not work. We would like to produce some $Q$ which has a “new” prime divisor of the form $4k+3$, and these do not necessarily. For instance, $3\cdot 7\cdot 11+1=2^3\cdot 29$ and $29\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}4$. Similarly, $3\cdot 7-1=2^2\cdot 5$. Perhaps the plus and minus $1$ cases can switch off, each providing a new prime in its turn… but no, $$3\cdot 7\cdot 11\cdot 19\cdot 23+1=2^2\cdot 25237$$

(with $25237\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}4$) while $$3\cdot 7\cdot 11\cdot 19\cdot 23-1=2\cdot 17\cdot 2969$$

(with $2969\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}4$).

Sticking to this general Euclidean train of logic, we might hope that there is some sort of $Q$ that is useful in this argument. We want a $Q$ which grants us a prime divisor of the form $4k+3$, so somehow it must be impossible for all the prime divisors be of the form $4k+1$ (if we can avoid divisibility by $2$, all the better). Were it to be the case that all the prime divisors of $Q$ had the form $4k+1$, then $$Q=(4k_1+1)\cdots (4k_M+1)=4(\dots )+1,$$

i.e. $Q$ must be of the form $4K+1$. We can choose a form for $Q$ which explicitly forbids this possibility. If we enumerate the, assumedly finite, set of $4k+3$ primes as $\{p_1,\dots ,p_N\}$, with $p_1=3$, $p_2=7$, $p_3=11$, …, then we may try $$Q=4p_1\cdots p_N+3.$$

If we take $Q$ in this form, then it has two beneficial features: (1) $Q$ is odd, so $2\nmid Q$, and (2) $Q\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}4$, so not all prime divisors of $Q$ may be of the form $4k+1$.

Therefore $Q$ looks like what we need, but does it actually provide us with new $4k+3$ primes when we factor it? Well… no. $4p_1+3=3\cdot 5$, so it gives us nothing new there: it repeats $3$ from the list and $5$ is not of the $4k+3$ form. Will it happen in general that a prime divisor $Q$ will be repeated from the list? Suppose $p$ is a $4k+3$ prime which divides $Q$ but also belongs to the finite list. Then $$p\mid (Q-4p_1\cdots p_N)=3,$$

which means that this can only happen if the prime in question is $3$. Still, that is enough to destroy the argument, because we do not necessarily produce a new $4k+3$ prime. There is a way out, which is to just skip $3$ in the product of the known-prime set. In that case, we will never get $3\mid Q$ because if $$Q=4p_2\cdots p_N+3,$$

then a prime $p$ dividing $Q$ must also divide $Q-3=4p_2\cdots p_N$. We have omitted $3$ from the product, though, so $p$ cannot be $3$. This, therefore, is the desired form for $Q$.

Summing up: Suppose there are only finitely many primes of the form $4k+3$, and enumerate them as $\{p_1,\dots ,p_N\}$ where $p_1=3$, $p_2=7$, $p_3=11$, and so on. Consider the quantity $$Q=4p_2\cdots p_N+3,$$

where we intentionally omit $p_1$ from the product. We see that $Q$ is odd, so that $2\nmid Q$ and all prime divisors of $Q$ must be of the form $4k+1$ or $4k+3$ for some integer $k$. It is impossible that all of the prime divisors of $Q$ be of the form $4k+1$, because their product would be $1$ modulo $4$, whereas $Q$ is clearly $3$ modulo $4$. Hence there exists a prime divisor $p\mid Q$ with $p\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}4$. Suppose that $p$ also belongs to the set $\{p_1,\dots ,p_N\}$, then we must have $$p\mid (Q-4p_2\cdots p_N)=3,$$

i.e. $p=3$. This is impossible, because if $3\mid Q$, then $3\mid (Q-3)=4p_2\cdots p_N$ which we know to be false (we purposely omitted $p_1=3$ for just this purpose). Hence $p$ does not belong to the list of “known” $4k+3$ primes, so it is a new one and the finite list is incomplete. Therefore there are infinitely many primes of the form $4k+3$, $k\in \mathbb{Z}$.

Herstein 3.8.7*: Prove that there are infinitely many primes of the form $4k+1$ with $k\in \mathbb{Z}$.

We have a couple of results from the chapter on primes of the form $4k+1$. For instance, we know from Lemma 3.8.2 that if $p$ is a prime of the form $4k+1$, then there exists $x\in \mathbb{Z}$ with $x^2\equiv -1\mathrm{m}\mathrm{o}\mathrm{d}p$. On the other hand, in problem 3.8.4 we showed that this is not true for primes of the form $4k+3$. Of course, all odd primes fall into one of the two classes, so for $p>2$ prime, $p$ has the form $4k+1$ if and only if there is a solution $x$ to $x^2\equiv -1\mathrm{m}\mathrm{o}\mathrm{d}p$.

We would like to make use of the Euclidean approach again, somehow exploiting the property just described. One way to do this is to suppose there are only finitely many $4k+1$ primes, say $\{p_1,\dots ,p_N\}$ with $p_1=5$, $p_2=13$, etc., and to construct $$Q=(p_1\cdots p_N{)}^2+1.$$

We note immediately that $Q$ is even, so it will always have a factor of $2$ which is not of interest to us. Of course, $Q$ is larger than two, so it will also have odd prime divisors. Let $p$ be an odd prime divisor of $Q$. Working in the same way as before, we say that $p$ may not belong to the old list, because if it did then $$p\mid (Q-(p_1\cdots p_N{)}^2)=1,$$

which is no good. Therefore $p$ is an odd prime which does not belong to the list. Moreover, we see that $x=p_1\cdots p_N$ is an integer such that $$x^2=Q-1\equiv -1\mathrm{m}\mathrm{o}\mathrm{d}p,$$

so that $p$ must be of the form $4k+1$. Thus we have exhibited a new $4k+1$ prime and there must be infinitely many.

Herstein 3.8.8*: Determine all of the prime elements in $\mathbb{Z}[i]$.

A prime element $p\in \mathbb{Z}[i]$ is one such that if $a,b\in \mathbb{Z}[i]$ satisfy $p=ab$, then one of $a$ or $b$ is a unit. We showed in problem 3.8.1 that the units of $\mathbb{Z}[i]$ are $\pm 1$ and $\pm i$. We may restrict attention to the first quadrant of the complex plane (including the positive real axis), because Gaussian integers in the other quadrants are all associates of Gaussian integers in the restricted set.

First consider the elements of $\mathbb{Z}$. Of course, if $n$ is composite in $\mathbb{Z}$, then it is still composite in $\mathbb{Z}[i]$. Turning to prime integers, we have that $$2=(1+i)(1-i),$$

so $2$ is not prime in $\mathbb{Z}[i]$. Similarly, if $k\in \mathbb{Z}$ and $p=4k+1$ is a prime in $\mathbb{Z}$, then by Theorem 3.8.2 there exist $a,b\in \mathbb{Z}$ such that $p=a^2+b^2$. Then we have $p=(a+bi)(a-bi)$ and so $4k+1$ primes are composite in $\mathbb{Z}[i]$. On the other hand, $4k+3$ primes are prime in $\mathbb{Z}[i]$: Suppose that $k\in \mathbb{Z}$ and $p=4k+3$ is a prime in $\mathbb{Z}$ but that it factors as $$p=(a+bi)(c+di)$$

in $\mathbb{Z}[i]$. Then, considering the norm of the equation, we have $$p^2=(a^2+b^2)(c^2+d^2)$$

which gives three possibilities for the value of $a^2+b^2$. If $a^2+b^2=1$, then $a+bi$ is a unit; if $a^2+b^2=p^2$, then $c^2+d^2=1$ so $c+di$ is a unit. Otherwise $a^2+b^2=p$, but we know from problem 3.8.5 that this is impossible because $p\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}4$. Therefore one of $a+bi$ or $c+di$ is a unit, so a $4k+3$ prime is again prime in the Gaussian integers. Of course, $-p$, $ip$ and $-ip$ are Gaussian primes as well.

Now we consider the primality of $a+bi$ with $a,b>0$. It’s not immediately clear what the condition should be, although it is pretty clear that primes of this type exist — for instance, $1+i$ is of such small norm that we can easily see it is prime. Consider a factorization $a+bi=(r+si)(t+ui)$ whose norm gives $$a^2+b^2=(r^2+s^2)(t^2+u^2)\mathrm{.}$$

One case jumping out at us here is that where $a^2+b^2$ is prime. If $a^2+b^2$ is prime, then one of the factors must be a unit because it will have a norm of $1$. In other words, if the norm of $a+bi$ is prime in $\mathbb{Z}$, then $a+bi$ is prime in $\mathbb{Z}[i]$ (we still require $a,b>0$). Playing around with Gaussian integers (and Mathematica’s handy ability to factor them and check their primality), one can easily be convinced that this condition is not only sufficient but also necessary.

The conjecture is then: if $a,b>0$, then $a+bi$ is prime in $\mathbb{Z}[i]$ if and only if $a^2+b^2$ is prime in $\mathbb{Z}$. Half of this result was proven in the preceding paragraph. We now seek to prove that if $a+bi$ is prime in $\mathbb{Z}[i]$, then $a^2+b^2$ is a prime integer. We have $$(a+bi)(a-bi)=a^2+b^2=p_1\cdots p_N,$$

where we have factored $a^2+b^2$ into primes in $\mathbb{Z}$. By Lemma 3.7.6, there is a prime $p\in \{p_1,\dots ,p_N\}$ with $(a+bi)\mid p$. Notice that we must be very careful here. It is tempting to say the opposite, that one of the $p$’s must divide $(a+bi)$, but this is not true because $p$ may not be prime in $\mathbb{Z}[i]$. Carrying on, we have that $(a+bi)\mid p$, so there are $x,y\in \mathbb{Z}$ with $$(a+bi)(x+yi)=p\mathrm{.}$$

Taking the complex conjugate, we also see that $(a-bi)\mid p$. Therefore $$a^2+b^2=(a+bi)(a-bi)\mid p^2$$

which forces $a^2+b^2=1$, $p$ or $p^2$. The condition $a,b>0$ forbids the first choice. If $a^2+b^2=p^2$, then we can consider $$p\cdot p=(a+bi)(x+yi)(a-bi)(x-yi)=p^2(x^2+y^2)$$

which forces $x+yi$ to be a unit. In that case, $(a+bi)(x+yi)=p$ forces $a+bi$ to lie along an axis, contradicting the supposition that $a,b>0$. Therefore $a^2+b^2\mathrm{\ne }{p}^2$ and we are left with the conclusion that $a^2+b^2$ is a prime.

Summing up: We have restricted attention to the first quadrant and the positive real axis, all the while understanding that the results in that quadrant will be mirrored to the other three quadrants (because they are related to the first by multiplication by the units $i$, $i^2$, $i^3$). The general conditions resulting from the analysis may be stated:

The Gaussian integer $a+bi$ is prime if and only if

• $ab=0$ and $a+b$ is a $4k+3$ prime (i.e. a $4k+3$ prime along any axis), or
• $ab\mathrm{\ne }0$ and $a^2+b^2$ is prime in $\mathbb{Z}$ (so it can be $2$ or a $4k+1$ prime).

Herstein 3.8.9*: Which positive integers can be written as a sum of two squares?

Let $a,x,y\in \mathbb{Z}$ be such that $a=x^2+y^2$. We can then consider the Gaussian integer $x+yi$ which has norm equal to $a$. By Theorem 3.7.2 (Euclidean rings are unique factorization domains), we can factor $x+yi$ as a product of Gaussian primes $\{{\pi }_i\}$, $$x+yi={\pi }_1\cdots {\pi }_N\mathrm{.}$$

Now, having classified the primes in problem 3.8.8, we can say that each ${\pi }_i$ can have a norm equal to either $2$, a $4k+1$ prime, or to the square of a $4k+3$ prime. Therefore, the integer $a$ will be some product of twos, $4k+1$ primes and squares of $4k+3$ primes. Of course, $a$ always has a prime factorization, so the only true restriction here is that the $4k+3$ primes must come in as even powers. Now we have seen that any $a$ expressible as a sum of two squares can be written in this form, but we still would like to show that every such product gives rise to something like $a$.

Let $\{p_1,\dots ,p_M\}$ be a collection of twos and $4k+1$ primes and let $\{q_1,\dots ,q_N\}$ be a collection of $4k+3$ primes. The integer $$A=p_1\cdots p_M{q}_1^2\cdots q_N^2$$

can easily be translated into the norm of a certain Gaussian integer: for each $p_i$, there exist $r_i,s_i\in \mathbb{Z}$ with $p_i=r_i^2+s_i^2$, so consider $$z=(r_1+i{s}_1)\cdots (r_M+i{s}_M)q_1\cdots q_N\mathrm{.}$$

We have that the norm of $z$ is $A$, so that $A$ is expressible as the sum of two squares.

Therefore, the positive integers expressible as a sum of two squares are exactly those for which $4k+3$ primes come into the prime factorization with only even powers.