Topics in Algebra, Chapter 3.8

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

Topics covered: 3.8

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

  • Theorem 3.8.1: Z[i] is a Euclidean ring. The distance function is d(a+bi)=a2+b2.

  • Lemma 3.8.1: Let c,pZ with p prime and (c,p)=1 such that there exist x,yZ with x2+y2=cp. Then there exist integers a,bZ such that p=a2+b2.

  • Lemma 3.8.2: If pZ is a prime of the form 4n+1, n an integer, then there exists xZ such that x21modp.

  • Theorem 3.8.2 (Fermat): If pZ is a prime of the form 4n+1, n an integer, then there exist a,bZ such that p=a2+b2.

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 Z[i].

Suppose a+biZ[i] is a unit, so there exists r+siZ[i] with 1=(a+bi)(r+si).

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)=a2+b2=1, and we easily enumerate the solutions as ±1,±i. These are the four units of Z[i].

Herstein 3.8.2: Prove that if a+biZ[i] is non-zero and is not a unit, then a2+b2>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 s0, we have that d(r)<d(rs). In particular, here we may say that 1=d(1)<d(1(a+bi))=a2+b2.

Herstein 3.8.3: Find the greatest common divisor in Z[i] of

(a) 3+4i and 43i.

(b) 11+7i and 18i.

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

(a) We will try to divide 43i 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 q0 such that 3+4i=q0(43i)+r1 with d(r1)<d(43i)=25. Drawing the two points on the complex plane gives a hint. 43i can be brought near to 3+4i by a rotation of π/2 about the origin, which is equivalent to a multiplication by i. Then we take q0=i.

But, oops! i(43i)=3+4i so we are already done. Their greatest common divisor is 43i (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 18i may be brought somewhat near to 11+7i if it is rotated by π/2, or equivalently, multiplied by i. A rotation by something like π/6 might be even better, but our choice should be fine. Thus we take q0=i and write 11+7i=i(18i)+1011i

so that r1=1011i. This is okay because d(r1)=221<325=d(18i). Drawing out the points 18i and 1011i, we really think a rotation by π/4 of 1011i would be helpful in this case. Of course, we can’t multiply by eiπ/4 because there is nothing like 2 in our ring. Taking the next best thing, we will try q1=1+i. Thus, we write 18i=(1+i)(1011i)3.

Then r2=3 and d(r2)=9<221=d(r1), so we have improved considerably.

Now a glance at 1011i=q2(3)+r3 suggests q2=3+4i and therefore r3=1+i. We have d(r3)=2<9=d(r2). Continuing, we can write 3=(1+i)(i1)1,

which puts q3=i1 and r4=1. At last, we are done, because r3=(1+i)r4. Therefore the greatest common divisor of 11+7i and 18i is 1, or equivalently 1: they are relatively prime. We can exhibit two Gaussian integers x,y such that (11+7i)x+(18i)y=1. They may be found by tracing backwards all of the steps of the algorithm, whereupon we find r4=(1+q0q1+q0q3+q2q3+q0q1q2q3)(18i)(q1+q3+q1q2q3)(11+7i).

Plugging in values, (6+i)(18i)+(66i)(11+7i)=1.

Herstein 3.8.4: Let p be a prime integer of the form 4k+3 with kZ. Prove that there can not be an xZ with x21modp.

Suppose that such an x existed, with x2+1=cp for some cZ. 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=a2+b2. Looking at this equation modulo 4, we find that it has no solutions: p3mod4 while squares modulo 4 can be only 0 or 1 so that a2+b2 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 kZ then (2k)2=4k20mod4, so even numbers will always square to zero modulo 4. On the other hand, (2k+1)2=4k2+4k+11mod4, 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 xp11modp,

where we have used the fact that px. Now, this may be rewritten as x4k+21modp.

On the other hand, from x21modp, we have that x4k+2x2(2k+1)(1)2k+11modp,

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 kZ. Prove that there do not exist a,bZ with p=a2+b2.

This was proven in the course of solving problem 3.8.4, where we consider the equation p=a2+b2 modulo 4.

Herstein 3.8.6: Prove that there are infinitely many primes of the form 4k+3 with kZ.

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, {p1,,pN}. Then construct P=p1pN 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 pQ and pP, so that p(QP)=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, 231113+1=59509.

Now we turn to the problem of primes of the form 4k+3. It is natural to consider things like Q=(4k1+3)(4kN+3)±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, 3711+1=2329 and 291mod4. Similarly, 371=225. Perhaps the plus and minus 1 cases can switch off, each providing a new prime in its turn… but no, 37111923+1=2225237

(with 252371mod4) while 371119231=2172969

(with 29691mod4).

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=(4k1+1)(4kM+1)=4()+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 {p1,,pN}, with p1=3, p2=7, p3=11, …, then we may try Q=4p1pN+3.

If we take Q in this form, then it has two beneficial features: (1) Q is odd, so 2Q, and (2) Q3mod4, 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. 4p1+3=35, 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(Q4p1pN)=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 3Q because if Q=4p2pN+3,

then a prime p dividing Q must also divide Q3=4p2pN. 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 {p1,,pN} where p1=3, p2=7, p3=11, and so on. Consider the quantity Q=4p2pN+3,

where we intentionally omit p1 from the product. We see that Q is odd, so that 2Q 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 pQ with p3mod4. Suppose that p also belongs to the set {p1,,pN}, then we must have p(Q4p2pN)=3,

i.e. p=3. This is impossible, because if 3Q, then 3(Q3)=4p2pN which we know to be false (we purposely omitted p1=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, kZ.

Herstein 3.8.7*: Prove that there are infinitely many primes of the form 4k+1 with kZ.

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 xZ with x21modp. 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 x21modp.

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 {p1,,pN} with p1=5, p2=13, etc., and to construct Q=(p1pN)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(Q(p1pN)2)=1,

which is no good. Therefore p is an odd prime which does not belong to the list. Moreover, we see that x=p1pN is an integer such that x2=Q11modp,

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 Z[i].

A prime element pZ[i] is one such that if a,bZ[i] satisfy p=ab, then one of a or b is a unit. We showed in problem 3.8.1 that the units of Z[i] are ±1 and ±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 Z. Of course, if n is composite in Z, then it is still composite in Z[i]. Turning to prime integers, we have that 2=(1+i)(1i),

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

in Z[i]. Then, considering the norm of the equation, we have p2=(a2+b2)(c2+d2)

which gives three possibilities for the value of a2+b2. If a2+b2=1, then a+bi is a unit; if a2+b2=p2, then c2+d2=1 so c+di is a unit. Otherwise a2+b2=p, but we know from problem 3.8.5 that this is impossible because p3mod4. 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 a2+b2=(r2+s2)(t2+u2).

One case jumping out at us here is that where a2+b2 is prime. If a2+b2 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 Z, then a+bi is prime in 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 Z[i] if and only if a2+b2 is prime in Z. Half of this result was proven in the preceding paragraph. We now seek to prove that if a+bi is prime in Z[i], then a2+b2 is a prime integer. We have (a+bi)(abi)=a2+b2=p1pN,

where we have factored a2+b2 into primes in Z. By Lemma 3.7.6, there is a prime p{p1,,pN} with (a+bi)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 Z[i]. Carrying on, we have that (a+bi)p, so there are x,yZ with (a+bi)(x+yi)=p.

Taking the complex conjugate, we also see that (abi)p. Therefore a2+b2=(a+bi)(abi)p2

which forces a2+b2=1, p or p2. The condition a,b>0 forbids the first choice. If a2+b2=p2, then we can consider pp=(a+bi)(x+yi)(abi)(xyi)=p2(x2+y2)

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 a2+b2p2 and we are left with the conclusion that a2+b2 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, i2, i3). 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
  • ab0 and a2+b2 is prime in 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,yZ be such that a=x2+y2. 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 {πi}, x+yi=π1πN.

Now, having classified the primes in problem 3.8.8, we can say that each π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 {p1,,pM} be a collection of twos and 4k+1 primes and let {q1,,qN} be a collection of 4k+3 primes. The integer A=p1pMq12qN2

can easily be translated into the norm of a certain Gaussian integer: for each pi, there exist ri,siZ with pi=ri2+si2, so consider z=(r1+is1)(rM+isM)q1qN.

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.