6

The Gaussian integers

P REVIEW
The Gaussian integers Z[i] are the simplest generalization of the or-
dinary integers Z and they behave in much the same way. In par-
ticular, Z[i] enjoys unique prime factorization, and this allows us to
reason about Z[i] the same way we do about Z. We do this because
Z[i] is the natural place to study certain properties of Z. In particu-
lar, it is the best place to examine sums of two squares, because in
Z[i] we can factorize a sum of two integer squares into linear factors:
x2 + y2 = (x − yi)(x + yi).
In the present chapter we use this idea to prove a famous theorem
of Fermat: if p > 2 is prime then p = a2 + b2 , for some natural
numbers a and b, if and only if p = 4n + 1 for some natural number
n. The Fermat two square theorem turns out to be related, not only
to unique prime factorization in Z[i], but also to the actual “primes”
of Z[i], the so-called Gaussian primes.
The Gaussian primes are easily shown to include the ordinary primes
that are not sums of two squares, and the factors a − bi and a + bi of
each ordinary prime of the form a2 + b2 . Unique prime factorization
in Z[i] establishes that these are the only Gaussian primes, up to
multiples by ±1 and ±i.
An easy congruence argument shows that ordinary primes of the
form 4n + 3 are not sums of two squares. The two square theorem
then shows that the primes that are sums of two squares are 2 and
all the remaining odd primes, namely, those of the form 4n + 1.
The proof of the two square theorem involves an important lemma
proved with the help of Wilson’s theorem: each prime p = 4n + 1

101
102 6 The Gaussian integers

divides a number of the form m2 + 1. Since m2 + 1 factorizes in Z[i],

it follows from unique prime factorization that p does also. The
factorization of p turns out to be of the form (a − bi)(a + bi), hence
p = (a − bi)(a + bi) = a2 + b2 , as claimed.

6.1 Z[i] and its norm

In the last chapter we saw that certain questions about Z are clarified by
√
working with generalized integers, in particular, working in Z[ n] to solve
√
x2 −ny2 = 1 in Z. The role of Z[ n] in this case is to allow the factorization
√ √
x2 − ny2 = (x − y n)(x + y n).

Similarly, when studying x2 + y2 , it helps to use the Gaussian integers

Z[i] = {a + bi : a, b ∈ Z}

because x2 + y2 = (x − yi)(x + yi).

Sums of two squares, x2 + y2 , are the oldest known topic in number
theory. We have already seen results about them found by the Babylonians,
Euclid, and Diophantus. In fact, it could be said that some properties of Z[i]
itself go back this far; at least, as far as Diophantus.
Diophantus apparently knew the two square identity (Section 1.8)

(a21 + b21 )(a22 + b22 ) = (a1 a2 − b1 b2 )2 + (a1 b2 + b1 a2 )2

because he knew that the product of sums of two squares is itself the sum
of two squares. Today we recognize this formula as equivalent to the mul-
tiplicative property of absolute value,

|z1 ||z2 | = |z1 z2 |,

where z1 = a1 + b1 i and z2 = a2 + b2 i. And Diophantus’ identity is exactly

the formula

norm(a1 + b1 i)norm(a2 + b2 i) = norm((a1 + b1 i)(a2 + b2 i)), (*)

where “norm” denotes the norm of Z[i],

norm(a + bi) = |a + bi|2 = a2 + b2 .

6.2 Divisibility and primes in Z[i] and Z 103

Exercises
When discussing factorization there are always trivial factors, called units, that we
prefer to ignore. For example, in N the only unit is 1, in Z the units are 1 and −1,
and in Z[i] the units are the elements of norm 1.
6.1.1 Show that the units of Z[i] are ±1, ±i.
√
Likewise,
√ the units of Z[ n] are its elements of norm 1, that is, the numbers
a + b n with a2 − nb2 = 1.
√
6.1.2 Describe the units of Z[ 2].
√
6.1.3 Show that Z[ n] has infinitely many units for any nonsquare natural num-
ber n.

6.2 Divisibility and primes in Z[i] and Z

The Z[i] norm
norm(a + bi) = |a + bi|2 = a2 + b2
is more useful in number theory than the absolute value because the norm
is always an ordinary integer. The multiplicative property of the norm (*)
implies that, if a Gaussian integer α divides a Gaussian integer γ , that is, if

γ = αβ for some β ∈ Z[i],

then
norm(γ ) = norm(α )norm(β ),
that is, norm(α ) divides norm(γ ).
Because of this, questions about divisibility in Z[i] often reduce to
questions about divisibility in Z. In particular, it is natural to define a
Gaussian prime to be a Gaussian integer that is not the product of Gaus-
sian integers of smaller norm. Then we can answer various questions about
Gaussian primes by looking at norms.
Examples.

1. 4 + i is Gaussian prime.
Because norm(4 + i) = 16 + 1 = 17, which is a prime in Z. Hence
4+i is not the product of Gaussian integers of smaller norm, because
no such norms divide 17.
104 6 The Gaussian integers

2. 2 is not a Gaussian prime.

Because 2 = (1 − i)(1 + i) and both 1 − i and 1 + i have norm 2,
which is smaller than norm(2) = 4.

3. 1 − i, 1 + i are Gaussian prime factors of 2.

Because norm(1 − i) = norm(1 + i) = 2 is a prime in Z, hence 1 − i
and 1 + i are not products of Gaussian integers of smaller norm.

Prime factorization in Z[i]. Any Gaussian integer factorizes into Gaus-

sian primes. The proof is similar to the proof in Z.

Proof. Consider any Gaussian integer γ . If γ itself is a Gaussian prime,

then we are done. If not, then γ = αβ for some α , β ∈ Z[i] with smaller
norm. If α , β are not both Gaussian primes, we factorize into Gaussian
integers of still smaller norm, and so on. This process must terminate since
norms, being natural numbers, cannot decrease forever. Hence we eventu-
ally get a Gaussian prime factorization of γ . 2

As in Z, it is not immediately clear that the prime factorization is

unique. However, we see in Section 6.4 that unique prime factorization
holds in Z[i] for much the same reasons as in Z.

Exercises
An equivalent way to define Gaussian primes, in line with a common way of
defining ordinary primes, is to say that ϖ is a Gaussian prime if ϖ is divisible
only by units and units times ϖ . (It is conventional to use the Greek letter pi to
denote primes in Z[i] and other generalizations of Z, the way p is used to denote
ordinary primes. However, to avoid confusion with π = 3.14159 . . . I prefer to use
ϖ , the variant form of pi.)

6.2.1 Explain why this definition is equivalent to the one above.

6.2.2 Prove that 3 is a Gaussian prime by considering the divisors of norm(3).

Ordinary primes are not always Gaussian primes, as we have already seen in
the case of 2. In fact, 2 is “almost a square” in Z[i].

6.2.3 Show that a unit times 2 is a square in Z[i].

6.2.4 Factorize 17 and 53 in Z[i].

6.3 Conjugates 105

6.3 Conjugates
The conjugate of z = a + bi is z = a − bi. The basic properties of conjuga-
tion (not only in Z[i] but for all complex numbers z) are

zz = |z|2 ,
z1 + z2 = z1 + z2 ,
z1 − z2 = z1 − z2 ,
z1 × z2 = z1 × z2 .

These can be checked by writing z1 = a1 + b1 i, z2 = a2 + b2 i and working

out both sides of each identity. We use these properties of conjugation to
take the first step towards a classification of Gaussian primes.
Real Gaussian primes. An ordinary prime p ∈ N is a Gaussian prime ⇔
p is not the sum of two squares. (And obviously p < 0 is a Gaussian prime
⇔ −p ∈ N is a Gaussian prime.)
Proof. (⇐) Suppose that we have an ordinary prime p that is not a Gaus-
sian prime, so it factorizes in Z[i]:

p = (a + bi)γ ,

where a + bi and γ are Gaussian integers with norm < the norm p2 of p
(and hence also of norm > 1). Taking conjugates of both sides we get

p = (a − bi)γ ,

since p is real and hence p = p. Multiplying these two expressions for p

gives

p2 = (a − bi)(a + bi)γγ
= (a2 + b2 )|γ |2 ,

where both a2 + b2 , |γ |2 > 1. But the only such factorization of p2 is pp,

hence p = a2 + b2 .
(⇒) Conversely, if an ordinary prime p equals a2 + b2 with a, b ∈ Z
then p is not a Gaussian prime because it has the Gaussian prime factor-
ization
p = (a − bi)(a + bi)
into factors of norm a2 + b2 = p < norm(p) = p2 . 2
106 6 The Gaussian integers

Notice also that the factors a − bi and a + bi of p are Gaussian primes

because their norm is the prime number a2 + b2 = p. Moreover, all Gaus-
sian primes a + bi, where a, b = 0, come in conjugate pairs like this. This is
so because if one member of the pair factorizes into αβ then its conjugate
factorizes into αβ .
What is not yet clear is whether all Gaussian primes a + bi with a, b
nonzero are factors of ordinary primes p = a2 + b2 . It is conceivable that
a + bi could be a Gaussian prime while a2 + b2 is a product of two or more
ordinary primes. In Section 6.4 we rule this out with the help of unique
prime factorization in Z[i].
At any rate, we can see that further clarification of the nature of Gaus-
sian primes depends on finding another way to describe the ordinary primes
that are sums of two squares. We saw in Section 3.7 (Example 1) that or-
dinary primes that are not sums of two squares are of the form 4n + 3. The
complement to this result—that any prime of the form 4n + 1 is a sum of
two squares—is a famous theorem discovered by Fermat. It is proved in
Section 6.5.

Exercises
6.3.1 Verify the basic properties of conjugation mentioned above.

The proof of the classification of real Gaussian primes has the following in-
teresting consequences.
6.3.2 Show that each ordinary prime has a distinct Gaussian prime associated
with it.
6.3.3 Deduce that there are infinitely many Gaussian primes.
Since the real positive Gaussian primes are those of the form 4n + 3, another
way to prove that there are infinitely many Gaussian primes is to show that there
are infinitely many ordinary primes of the form 4n + 3. The proof is along lines
similar to Euclid’s proof in Section 1.1.
6.3.4 Show that the product of numbers of the form 4n + 1 is of the same form.
Deduce that any number of the form 4n + 3 has a prime divisor of the form
4n + 3.
6.3.5 If p1 , p2 , . . . , pk are primes of the form 4n + 3, show that 2p1 p2 · · · pk + 1 is
also of the form 4n + 3.
6.3.6 Deduce from Exercises 6.3.4 and 6.3.5 that there are infinitely many primes
of the form 4n + 3.
6.4 Division in Z[i] 107

6.4 Division in Z[i]

Unique prime factorization in Z[i], as in Z, relies on the Euclidean algo-
rithm, which depends in turn on:
Division property of Z[i]. If α , β = 0 are in Z[i] then there is a quotient µ
and a remainder ρ such that

α = µβ + ρ with |ρ | < |β |.

Proof. This property becomes obvious once one sees that the Gaussian
integer multiples µβ of any Gaussian integer β = 0 form a square grid in
the complex plane.
This is because multiplication of β by i rotates the vector from 0 to β
through 90◦ , hence 0, β , and iβ are three corners of a square. All other
multiples of β are sums (or differences) of β and iβ , hence they lie at the
corners of a square grid. (Figure 6.1.)

iβ
β

Figure 6.1: Multiples of a Gaussian integer

Any Gaussian integer α lies in one of these squares, and there is a

nearest corner µβ (not necessarily unique, but no matter). Then

α = µβ + ρ , where |ρ | = distance to nearest corner,

so |ρ | is less than the side of a square, namely |β |. 2

Thanks to the division property we have
1. A Euclidean algorithm for Z[i]

2. gcd(α , β ) = µα + νβ for some µ , ν ∈ Z[i].

108 6 The Gaussian integers

3. The prime divisor property: if a prime ϖ divides αβ then ϖ divides

α or ϖ divides β .
4. Unique prime factorization up to order and factors of norm 1, namely
±1 and ±i. Elements of norm 1 are called units and unique prime
factorization usually comes with the qualification “up to unit fac-
tors”. This is true even in Z, where the units are ±1 and hence
primes may vary up to sign.
As a first application of unique prime factorization in Z[i] we complete
the description of Gaussian primes begun in Section 6.3. There we found
that the real Gaussian primes are ordinary primes that are not sums of two
squares, and their negatives. It is also clear that the pure imaginary Gaus-
sian primes are of the form ±ip, where p is a real Gaussian prime. Thus it
remains to describe the Gaussian primes a + bi with a, b nonzero.
Imaginary Gaussian primes. The Gaussian primes a+bi with a, b nonzero
are factors of ordinary primes p of the form a2 + b2 .
Proof. First, as noted in Section 6.3, if a + bi is a Gaussian prime then so
is a − bi (because if a − bi = αβ is not prime, neither is a + bi = αβ ).
Next, (a − bi)(a + bi) is a (necessarily unique) Gaussian prime factor-
ization of
p = a2 + b2 = (a − bi)(a + bi).
But p must then be an ordinary prime. Indeed, if
p = rs with 1 < r, s < p and r, s ∈ Z,
then the Gaussian prime factors of r and s give a Gaussian prime factoriza-
tion of p different from (a − bi)(a + bi) (either two real factors r and s, or
≥ four complex factors). 2

Exercises
Using unique prime factorization we can prove results on squares and cubes in
Z[i], similar to those on squares and cubes in N proved in Section 2.5. The only
difference is that we have to take account of units, as indeed we already do in Z.
6.4.1 Is it true in Z that relatively prime factors of a square are themselves squares?
If not, how should the statement be modified to make it correct?
6.4.2 Show that relatively prime factors of a cube in Z are themselves cubes.
6.4.3 Formulate a theorem about relatively prime factors of a square in Z[i].
6.4.4 Show that relatively prime factors of a cube in Z[i] are themselves cubes.
6.5 Fermat’s two square theorem 109

6.5 Fermat’s two square theorem

In Section 3.7 we used congruence mod 4 to show that primes of the form
4n + 3 are not sums of two squares. Fermat’s two square theorem says that
the remaining odd primes—those of the form 4n + 1—are all sums of two
squares.
We apply the theory of Z[i] to a prime p = 4n + 1 with the help of an
m ∈ Z such that p divides m2 + 1. Such an m always exists by a result of
Lagrange (1773) that follows from Wilson’s theorem in Section 3.5: for
any prime p

1 × 2 × 3 × · · · × (p − 1) ≡ −1 (mod p).

Lagrange’s lemma. A prime p = 4n + 1 divides m2 + 1 for some m ∈ Z.

Proof. If we apply Wilson’s theorem to the prime p = 4n + 1 we get

−1 ≡ 1 × 2 × 3 × · · · × 4n (mod p)
≡ (1 × 2 × · · · × 2n)×
((2n + 1) × · · · × (4n − 1) × (4n)) (mod p)
≡ (1 × 2 × · · · × 2n)×
((−2n) × · · · × (−2)(−1)) (mod p) since p − k ≡ −k (mod p)
≡ (1 × 2 × · · · × 2n) (−1)
2 2n
(mod p)
≡ (1 × 2 × · · · × 2n)2 (mod p)

Taking m = (2n)! we get m2 ≡ −1 (mod p). That is, p divides m2 + 1. 2

Fermat’s two square theorem. If p = 4n + 1 is prime, then p = a2 + b2
for some a, b ∈ Z.
Proof. Given p, let m ∈ Z be such that p divides m2 + 1, as in the lemma.
In Z[i], m2 + 1 has the factorization

m2 + 1 = (m − i)(m + i).

And, even though p divides m2 +1, p does not divide m−i or m+i because
p − p and p + p are not Gaussian integers.
m i m i

By the Gaussian prime divisor property of Section 6.4, it follows that

p is not a Gaussian prime. But then p = a2 + b2 , as proved in Section 6.3.
2
110 6 The Gaussian integers

It also follows that

p = (a − bi)(a + bi)
is a factorization into Gaussian primes, and we now know that any such
factorization is unique. So in fact we have a stronger form of Fermat’s two
square theorem: each prime p = 4n + 1 is a sum a2 + b2 of two squares for
a unique pair of natural numbers a, b.

Exercises
Here is another way in which Z[i] throws light on sums of two squares. The
following exercises develop a proof of a theorem of Euler (1747): if gcd(a, b) = 1
then any divisor of a2 + b2 is of the form c2 + d 2 where gcd(c, d) = 1. The main
steps depend on unique prime factorization in Z[i].
6.5.1 Give an example that shows why the condition gcd(a, b) = 1 is necessary.
6.5.2 Show that each integer divisor e > 1 of a2 + b2 is a product of Gaussian
prime divisors q + ir of a2 + b2 , unique up to unit factors.
6.5.3 Show that each of the Gaussian primes q + ir divides either a − ib or a + ib.
Deduce that none of them is an ordinary prime p.
6.5.4 Show that, along with each Gaussian prime factor q + ir of e, its conjugate
q − ir is also a factor.
6.5.5 Deduce from Exercise 6.5.4 that e is of the form c2 +d 2 where c+di divides
a + bi.
6.5.6 Deduce from Exercise 6.5.5 that gcd(c, d) = 1.

6.6 Pythagorean triples

Now is a good time to revisit the primitive Pythagorean triples, whose re-
lationship with Z[i] was suggested in Section 1.8. Since odd squares are
congruent to 1 (mod 4) and even squares are congruent to 0 (mod 4), a sum
of two odd squares is not a square. Hence in a primitive triple (x, y, z) one
of x, y is even and z is odd. The argument in Section 1.8 was that if
x2 + y2 = z2
then
(x − yi)(x + yi) = z2 ,
so x − yi and x + yi are Gaussian prime factors of an odd square, z2 . Then
we wanted to say that:
6.6 Pythagorean triples 111

1. If x and y are relatively prime (in Z) then so are x − yi and x + yi (in

Z[i]).

2. In Z[i], relatively prime factors of a square are squares.

The first statement is correct. If gcd(x, y) = 1 in Z then gcd(x, y) = 1 in

Z[i]. This is so since a common Gaussian prime divisor is accompanied by
its conjugate, and their product is a common divisor >1 in Z. A common
divisor of x − yi and x + yi also divides their sum 2x and difference 2iy.
Therefore, since gcd(x, y) = 1, any common prime divisors of x − iy and
x + iy are primes ±1 ± i dividing 2. No such divisors are present, since they
imply that (x − iy)(x + iy) = z2 is even.
The second statement is not quite correct, but the following amendment
of it is: relatively prime factors of a square are squares, up to unit factors.
This follows from unique prime factorization in Z[i].
Since x − yi and x + yi have no common Gaussian prime factor, while
each prime factor of z2 occurs to an even power, each prime factor of x − yi,
and each prime factor of x+yi, must also occur to an even power. A product
of primes, each occurring to an even power, is obviously a square (compare
with the same argument for natural numbers in Section 2.5). Hence each of
x − yi and x + yi is a unit times a square, since their only possible nonprime
factors are units. 2
The amended second statement is good enough to give us the conclu-
sion we expect. We have shown that x − yi is a unit times a square, hence
it is one of

(s − ti)2 , −(s − ti)2 , i(s − ti)2 , −i(s − ti)2 , for some s,t ∈ Z.

That is, it is one of

(s2 − t 2 ) − 2sti, t 2 − s2 + 2sti, 2st + (s2 − t 2 )i, −2st + (t 2 − s2 )i.

In each case, equating real and imaginary parts gives one of x and y in
the form u2 − v2 and the other in the form 2uv for some natural numbers
u and v. Thus the result is essentially the same as that obtained by the
loose argument in Section 1.8, but better, because it does not force the
even member of the pair, 2uv, to be first.
Moreover, we necessarily have gcd(u, v) = 1 because any common
prime divisor of u and v is a common divisor of u2 − v2 and 2uv, hence
of x and y. Thus the correct outcome of the speculation in Section 1.8 is:
112 6 The Gaussian integers

Primitive Pythagorean triples. If x2 + y2 = z2 for some relatively prime

natural numbers x and y, then one of x and y is of the form u2 − v2 and the
other of the form 2uv, for relatively prime natural numbers u and v. 2
We also find in each case that z = u2 + v2 , because
(u2 − v2 )2 + (2uv)2 = u4 + 2u2 v2 + v4 = (u2 + v2 )2 .
Thus z is a sum of two squares. Since u and v are any relatively prime
numbers, and a prime u2 + v2 necessarily has gcd(u, v) = 1, z can be any
prime sum of two squares. Thus we get a geometric characterization of the
primes that are sums of two squares.
Prime hypotenuses. The primes that are sums of two squares are those
that occur as hypotenuses of right-angled triangles with integer sides. 2

Exercises
The last result, together with Fermat’s two square theorem, shows that the primes
of the form 4n + 1 are precisely those occurring as hypotenuses of integer right-
angled triangles.
6.6.1 Find integer right-angled triangles with hypotenuses 5, 13, 17 (you should
know these), and 29, 37, and 41.
6.6.2 Given a prime p = 4n + 1, is the integer right-angled triangle with hy-
potenuse p unique?
The argument above shows that, if (x, y, z) is a primitive Pythagorean triple,
then x + yi is a unit times a square in Z[i]. But once we know that x = u2 − v2 ,
y = 2uv we can say more.
6.6.3 If (x, y, z) is a primitive Pythagorean triple with x odd, show that x + yi is a
square in Z[i].
6.6.4 Verify directly that 3 + 4i is a square in Z[i].
It should be clear from your answer to Question 6.6.3 that finding the pa-
rameters u and v for a given primitive Pythagorean triple (x, y, z), with x odd, is
equivalent to finding the square root(s) of a complex number.
6.6.5 Find the square root of 5 + 12i.
6.6.6 If you have some software for computing square roots of complex numbers,
verify that each entry (x, y, z) in Plimpton 322 (Section 1.6), except the
triple (60, 45, 75), yields a y+xi that is a square in Z[i]. (Note: this includes
the last triple (90, 56, 106), which is clearly not primitive.)
6.6.7 Explain how to compute the square root of a complex number by hand,
using quadratic equations.
6.7 ∗ Primes of the form 4n + 1 113

6.7 ∗ Primes of the form 4n + 1

Lagrange’s lemma, proved in the Section 6.5, is actually half of an impor-
tant result concerning the so-called “quadratic character of −1” that we
study further in Chapter 9. Here we use it to prove that there are infinitely
many primes of the form 4n + 1, complementing the corresponding easy
result about primes of the form 4n + 3 proved in Exercises 6.3.4–6.3.6.
Quadratic character of −1. The congruence x2 ≡ −1 (mod p), where p
is an odd prime, has a solution precisely when p = 4n + 1.
Proof. When p = 4n + 1, Lagrange’s lemma gives an x with x2 ≡ −1 (mod
p). To show that x2 ≡ −1 (mod p) has no solution when p = 4n + 3 we
suppose, on the contrary, that it does.
If
x2 ≡ −1 (mod p = 4n + 3)
then raising both sides to the power 2n + 1 gives
(x2 )2n+1 ≡ (−1)2n+1 ≡ −1 (mod p = 4n + 3).
Since 2(2n + 1) = 4n + 2 = p − 1, this says that
x p−1 ≡ −1 (mod p),
contrary to Fermat’s little theorem. Hence x2 ≡ −1 (mod p) has no solution
when p = 4n + 3. 2
Thus solutions of x2 ≡ −1 (mod p) occur precisely when the odd prime
p is of the form 4n + 1. To put it another way: the odd primes p that divide
values of x2 + 1, for x ∈ Z, are precisely the primes p = 4n + 1.
Infinitude of primes 4n + 1. There are infinitely many primes of the form
p = 4n + 1.
Proof. From what we have just proved, it suffices to show that infinitely
many primes divide values of x2 + 1 for x ∈ Z. Suppose on the contrary
that only finitely many primes p1 , p2 , . . . , pk divide values of x2 + 1.
Now consider the polynomial
(p1 p2 · · · pk y)2 + 1 = g(y).
Clearly, any prime p that divides a value of g(y), for y ∈ Z, also divides
a value of x2 + 1 (namely, for x = p1 p2 · · · pk y). But none of p1 , p2 , . . . , pk
divides g(y), because each leaves remainder 1.
114 6 The Gaussian integers

Therefore, no prime divides g(y), for any y ∈ Z, and hence the only
possible values of the integers g(y) are ±1. In other words,

(p1 p2 · · · pk y)2 + 1 = ±1 for all y ∈ Z.

But this is absurd, because each of the quadratic equations

(p1 p2 · · · pk y)2 + 1 = 1 and (p1 p2 · · · pk y)2 + 1 = −1

has at most two solutions y. This contradiction shows that x2 +1 is divisible

by infinitely many primes, as required. 2
It now follows, by Fermat’s two square theorem, that infinitely many
primes are sums a2 + b2 of two squares. Hence there are infinitely many
Gaussian primes a + ib that are neither real nor pure imaginary.

Exercises
The argument just used to prove that x2 + 1 is divisible by infinitely many primes
can be generalized to any nonconstant polynomial f (x) with integer coefficients.
We suppose that

f (x) = am xm + · · · + a1 x + a0 , where a0 , a1 , . . . , am ∈ Z and a0 , am = 0,

has values divisible only by the primes p1 , p2 , . . . , pk , and consider the polynomial

f (a0 p1 p2 · · · pk y) = a0 g(y),

where g(y) is a polynomial of degree m.

6.7.1 Show that g(y) has integer coefficients, constant term 1, and that any prime
dividing a value of g(y), for y ∈ Z, also divides a value of f (x), for x ∈ Z.
6.7.2 Show, however, that none of p1 , p2 . . . , pk divide g(y) when y ∈ Z.
6.7.3 Deduce from Exercise 6.7.2 that g(y) = ±1 for any y ∈ Z.
6.7.4 Show that the equations g(y) = 1 and g(y) = −1 have only finitely many
solutions, which contradicts Exercise 6.7.3. (Where have you assumed that
f (x) is nonconstant?)
This contradiction shows that f (x) is divisible by infinitely many primes. But
now notice: we did not assume that infinitely many primes exist, hence this is a
self-contained proof of Euclid’s theorem that there are infinitely many primes.
6.7.5 Is this argument essentially different from Euclid’s?
6.8 Discussion 115

6.8 Discussion
The two square theorem was stated without proof by Fermat in 1640,
though he claimed to have a proof by descent: assuming there is a prime
that is of the form 4n + 1 but not a sum of two squares he could show that
there is a smaller prime with the same property. The first known proof of
the theorem was in fact by descent, and published by Euler (1755). It cost
him several years of effort.
Today it is possible to give quite simple proofs with the help of the re-
sult we called Lagrange’s lemma in Section 6.5. Lagrange himself proved
this lemma by means of Fermat’s little theorem and his own theorem on
the number of solutions of congruences mod p (Section 3.5).
Lagrange (1773) used his lemma together with his theory of equiva-
lence of quadratic forms (Section 5.6) to give a new proof of the two square
theorem. The part of the proof involving quadratic forms was simplified by
Gauss (1801), long before his creation of the Gaussian integers. It seems
that Gauss had the main results about Z[i], including unique prime fac-
torization, around 1815, but they were first published in 1832. The proof
used in this chapter, combining unique prime factorization in Z[i] with La-
grange’s lemma, is due to Dedekind (1894).
Yet another popular proof uses the geometry of numbers, developed in
the 1890s by Minkowski. It may be found in Scharlau and Opolka (1985)
together with a historical introduction to Minkowski’s results.
Parallel to all the popular proofs of the two square theorem there are
analogous proofs of the four square theorem of Lagrange (1770): every
natural number is the sum of (at most) four natural number squares. Most
use the following counterpart of Lagrange’s lemma: any prime p divides
a number of the form l 2 + m2 + 1. The counterpart turns out to be easier.
What is harder is the four square identity discovered by Euler (1748b). It is
analogous to the two square identity of Section 6.1 but is much more com-
plicated (see Section 8.3). It can be mechanically checked by multiplying
out both sides, but what does it mean?
The Gaussian integer proof is favored in this book because Z[i] is a
natural structure and the two square identity is a natural part of it—the
multiplicative property of the norm—rather than an accidental identity of
formal expressions. In Chapter 8 we give a similar “structural” proof of
the four square theorem that uses the quaternion integers. These are a
remarkable four-dimensional structure from which the four square identity
116 6 The Gaussian integers

emerges naturally as the multiplicative property of the quaternion norm.

Again, the key to the proof is unique prime factorization (or rather the
prime divisor property, which happens to be somewhat easier than unique
prime factorization in the quaternion case).
Fermat’s two square theorem was generalized in another direction by
Fermat himself. In 1654 Fermat announced similar theorems on primes of
the forms x2 + 2y2 and x2 + 3y2 :

p = x2 + 2y2 ⇔ p = 8n + 1 or p = 8n + 3,
p = x2 + 3y2 ⇔ p = 3n + 1.

Our proof of the two square theorem in Section 6.5 can be adapted to Fer-
mat’s x2 + 2y2 and x2 + 3y2 theorems with the help √ of unique prime√fac-
torization theorems for numbers of the forms a + b −2 and a + b −3
respectively. Such theorems will be proved in the next chapter.
The other thing we need to adapt is Lagrange’s lemma: if p = 4n + 1
then p divides a number of the form m2 + 1 for some m ∈ Z. In Section
6.7 we described this lemma (together with its converse) as the quadratic
character of −1 because it says that −1 is congruent to a square mod p
precisely when p = 4n + 1.
To prove Fermat’s theorems on primes of the form x2 +2y2 and x2 +3y2
we similarly need the quadratic characters of −2 and −3. They are:

−2 ≡ square (mod p) ⇔ p = 8n + 1 or 8n + 3,
−3 ≡ square (mod p) ⇔ p = 3n + 1.

Instead of finding quadratic characters one by one, in Chapter 9 we prove

the sweeping law of quadratic reciprocity, which allows us to tell when
any integer is congruent to a square mod p. Quadratic reciprocity was
first observed by Euler and proved by him in special cases, such as those
involved in Fermat’s theorems. The first general proof is due to Gauss
(1801), and quadratic reciprocity has since been proved in many different
ways. In fact, it has been proved more often than any other theorem except
its distant ancestor, the Pythagorean theorem.
http://www.springer.com/978-0-387-95587-2