This page covers section 3.8 (“A Particular Euclidean Ring”).
, the Gaussian integers, is the set of complex numbers where . The proof of each result in this chapter is very clever.
Theorem 3.8.1: is a Euclidean ring. The distance function is .
Lemma 3.8.1: Let with prime and such that there exist with . Then there exist integers such that .
Lemma 3.8.2: If is a prime of the form , an integer, then there exists such that .
Theorem 3.8.2 (Fermat): If is a prime of the form , an integer, then there exist such that .
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.
Suppose is a unit, so there exists with
We have that and maps into the non-negative integers. This forces the norm of a unit to be . Then we have , and we easily enumerate the solutions as . These are the four units of .
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 elements of Euclidean ring and , we have that . In particular, here we may say that
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 ?
(a) We will try to divide into . We need to find a quotient that gives us a remainder small enough to be acceptable in the algorithm. That is, we seek such that with . Drawing the two points on the complex plane gives a hint. can be brought near to by a rotation of about the origin, which is equivalent to a multiplication by . Then we take .
But, oops! so we are already done. Their greatest common divisor is (or , 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 may be brought somewhat near to if it is rotated by , or equivalently, multiplied by . A rotation by something like might be even better, but our choice should be fine. Thus we take and write
so that . This is okay because . Drawing out the points and , we really think a rotation by of would be helpful in this case. Of course, we can’t multiply by because there is nothing like in our ring. Taking the next best thing, we will try . Thus, we write
Then and , so we have improved considerably.
Now a glance at suggests and therefore . We have . Continuing, we can write
which puts and . At last, we are done, because . Therefore the greatest common divisor of and is , or equivalently : they are relatively prime. We can exhibit two Gaussian integers such that . They may be found by tracing backwards all of the steps of the algorithm, whereupon we find
Plugging in values,
Suppose that such an existed, with for some . Then we fall into the case of Lemma 3.8.1 which says that may be expressed as a sum of two squares, . Looking at this equation modulo , we find that it has no solutions: while squares modulo can be only or so that can only take the values . This contradiction forces us to conclude that no such may exist.
It is easy to see that the only quadratic residues modulo are and . If then , so even numbers will always square to zero modulo . On the other hand, , so odd numbers will always square to modulo .
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 would have
where we have used the fact that . Now, this may be rewritten as
On the other hand, from , we have that
which is a contradiction. Hence no such exists.
This was proven in the course of solving problem 3.8.4, where we consider the equation modulo .
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, . Then construct and . Because any integer can be factored into primes, we know that has some prime divisor . If were to belong to the supposed set, however, then we would have and , so that which is not possible. Therefore necessarily has a prime divisor which does not belong to our list, so the list is incomplete whenever it is finite. Note that 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, .
Now we turn to the problem of primes of the form . It is natural to consider things like
but quick numerical investigations show that these do not work. We would like to produce some which has a “new” prime divisor of the form , and these do not necessarily. For instance, and . Similarly, . Perhaps the plus and minus cases can switch off, each providing a new prime in its turn… but no,
(with ) while
Sticking to this general Euclidean train of logic, we might hope that there is some sort of that is useful in this argument. We want a which grants us a prime divisor of the form , so somehow it must be impossible for all the prime divisors be of the form (if we can avoid divisibility by , all the better). Were it to be the case that all the prime divisors of had the form , then
i.e. must be of the form . We can choose a form for which explicitly forbids this possibility. If we enumerate the, assumedly finite, set of primes as , with , , , …, then we may try
If we take in this form, then it has two beneficial features: (1) is odd, so , and (2) , so not all prime divisors of may be of the form .
Therefore looks like what we need, but does it actually provide us with new primes when we factor it? Well… no. , so it gives us nothing new there: it repeats from the list and is not of the form. Will it happen in general that a prime divisor will be repeated from the list? Suppose is a prime which divides but also belongs to the finite list. Then
which means that this can only happen if the prime in question is . Still, that is enough to destroy the argument, because we do not necessarily produce a new prime. There is a way out, which is to just skip in the product of the known-prime set. In that case, we will never get because if
then a prime dividing must also divide . We have omitted from the product, though, so cannot be . This, therefore, is the desired form for .
Summing up: Suppose there are only finitely many primes of the form , and enumerate them as where , , , and so on. Consider the quantity
where we intentionally omit from the product. We see that is odd, so that and all prime divisors of must be of the form or for some integer . It is impossible that all of the prime divisors of be of the form , because their product would be modulo , whereas is clearly modulo . Hence there exists a prime divisor with . Suppose that also belongs to the set , then we must have
i.e. . This is impossible, because if , then which we know to be false (we purposely omitted for just this purpose). Hence does not belong to the list of “known” primes, so it is a new one and the finite list is incomplete. Therefore there are infinitely many primes of the form , .
We have a couple of results from the chapter on primes of the form . For instance, we know from Lemma 3.8.2 that if is a prime of the form , then there exists with . On the other hand, in problem 3.8.4 we showed that this is not true for primes of the form . Of course, all odd primes fall into one of the two classes, so for prime, has the form if and only if there is a solution to .
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 primes, say with , , etc., and to construct
We note immediately that is even, so it will always have a factor of which is not of interest to us. Of course, is larger than two, so it will also have odd prime divisors. Let be an odd prime divisor of . Working in the same way as before, we say that may not belong to the old list, because if it did then
which is no good. Therefore is an odd prime which does not belong to the list. Moreover, we see that is an integer such that
so that must be of the form . Thus we have exhibited a new prime and there must be infinitely many.
A prime element is one such that if satisfy , then one of or is a unit. We showed in problem 3.8.1 that the units of are and . 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 . Of course, if is composite in , then it is still composite in . Turning to prime integers, we have that
so is not prime in . Similarly, if and is a prime in , then by Theorem 3.8.2 there exist such that . Then we have and so primes are composite in . On the other hand, primes are prime in : Suppose that and is a prime in but that it factors as
in . Then, considering the norm of the equation, we have
which gives three possibilities for the value of . If , then is a unit; if , then so is a unit. Otherwise , but we know from problem 3.8.5 that this is impossible because . Therefore one of or is a unit, so a prime is again prime in the Gaussian integers. Of course, , and are Gaussian primes as well.
Now we consider the primality of with . It’s not immediately clear what the condition should be, although it is pretty clear that primes of this type exist — for instance, is of such small norm that we can easily see it is prime. Consider a factorization whose norm gives
One case jumping out at us here is that where is prime. If is prime, then one of the factors must be a unit because it will have a norm of . In other words, if the norm of is prime in , then is prime in (we still require ). 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 , then is prime in if and only if is prime in . Half of this result was proven in the preceding paragraph. We now seek to prove that if is prime in , then is a prime integer. We have
where we have factored into primes in . By Lemma 3.7.6, there is a prime with . Notice that we must be very careful here. It is tempting to say the opposite, that one of the ’s must divide , but this is not true because may not be prime in . Carrying on, we have that , so there are with
Taking the complex conjugate, we also see that . Therefore
which forces , or . The condition forbids the first choice. If , then we can consider
which forces to be a unit. In that case, forces to lie along an axis, contradicting the supposition that . Therefore and we are left with the conclusion that 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 , , ). The general conditions resulting from the analysis may be stated:
The Gaussian integer is prime if and only if
Let be such that . We can then consider the Gaussian integer which has norm equal to . By Theorem 3.7.2 (Euclidean rings are unique factorization domains), we can factor as a product of Gaussian primes ,
Now, having classified the primes in problem 3.8.8, we can say that each can have a norm equal to either , a prime, or to the square of a prime. Therefore, the integer will be some product of twos, primes and squares of primes. Of course, always has a prime factorization, so the only true restriction here is that the primes must come in as even powers. Now we have seen that any 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 .
Let be a collection of twos and primes and let be a collection of primes. The integer
can easily be translated into the norm of a certain Gaussian integer: for each , there exist with , so consider
We have that the norm of is , so that is expressible as the sum of two squares.
Therefore, the positive integers expressible as a sum of two squares are exactly those for which primes come into the prime factorization with only even powers.