CHAPTER ONE

FROM FERMAT TO GAUSS

§1. FERMAT, EULER AND QUADRATIC RECIPROCITY

In this section we will discuss primes of the form x2 + ny2, where n is a fixed positive integer. Our starting point will be the three theorems of Fermat for odd primes p

(1.1)

mentioned in the introduction. The goals of §1 are to prove (1.1) and, more importantly, to get a sense of what’s involved in studying the equation p = x2 + ny2 when n > 0 is arbitrary. This last question was best answered by Euler, who spent 40 years proving Fermat’s theorems and thinking about how they can be generalized. Our exposition will follow some of Euler’s papers closely, both in the theorems proved and in the examples studied. We will see that Euler’s strategy for proving (1.1) was one of the primary things that led him to discover quadratic reciprocity, and we will also discuss some of his remarkable conjectures concerning p = x2 + ny2 for n > 3. These conjectures touch on quadratic forms, composition, genus theory, cubic and biquadratic reciprocity, and will keep us busy for the rest of the chapter.

A. Fermat

Fermat’s first mention of p = x2 + y2 occurs in a 1640 letter to Mersenne [35, Vol. II, p. 212], while p = x2 + 2y2 and p = x2 + 3y2 come later, first appearing in a 1654 letter to Pascal [35, Vol. II, pp. 310–314]. Although no proofs are given in these letters, Fermat states the results as theorems. Writing to Digby in 1658, he repeats these assertions in the following form:

Every prime number which surpasses by one a multiple of four is composed of two squares. Examples are 5, 13, 17, 29, 37, 41, etc.

Every prime number which surpasses by one a multiple of three is composed of a square and the triple of another square. Examples are 7, 13, 19, 31, 37, 43, etc.

Every prime number which surpasses by one or three a multiple of eight is composed of a square and the double of another square. Examples are 3, 11, 17, 19, 41, 43, etc.

Fermat adds that he has solid proofs—“firmissimis demonstralibus” [35, Vol. II, pp. 402–408 (Latin), Vol. Ill, pp. 314–319 (French)].

The theorems (1.1) are only part of the work that Fermat did with x2 + ny2. For example, concerning x2 + y2, Fermat knew that a positive integer N is the sum of two squares if and only if the quotient of N by its largest square factor is a product of primes congruent to 1 modulo 4 [35, Vol. Ill, Obs. 26, pp. 256–257], and he knew the number of different ways N can be so represented [35, Vol. Ill, Obs. 7, pp. 243–246]. Fermat also studied forms beyond x2 + y2, x2 + 2y2 and x2 + 3y2. For example, in the 1658 letter to Digby quoted above, Fermat makes the following conjecture about x2 + 5y2, which he admits he can’t prove:

If two primes, which end in 3 or 7 and surpass by three a multiple of four, are multiplied, then their product will be composed of a square and the quintuple of another square.

Examples are the numbers 3, 7, 23, 43, 47, 67, etc. Take two of them, for example 7 and 23; their product 161 is composed of a square and the quintuple of another square. Namely 81, a square, and the quintuple of 16 equal 161.

Fermat’s condition on the primes is simply that they be congruent to 3 or 7 modulo 20. In §2 we will present Lagrange’s proof of this conjecture, which uses ideas from genus theory and the composition of forms.

Fermat’s proofs used the method of infinite descent, but that’s often all he said. As an example, here is Fermat’s description of his proof for p = x2 + y2 [35, Vol. II, p. 432]:

If an arbitrarily chosen prime number, which surpasses by one a multiple of four, is not a sum of two squares, then there is a prime number of the same form, less than the given one, and then yet a third still less, etc., descending infinitely until you arrive at the number 5, which is the least of all of this nature, from which it would follow was not the sum of two squares. From this one must infer, by deduction of the impossible, that all numbers of this form are consequently composed of two squares.

This explains the philosophy of infinite descent, but doesn’t tell us how to produce the required lesser prime. We have only one complete proof by Fermat. It occurs in one of his marginal notes (the area of a right triangle with integral sides cannot be an integral square [35, Vol. Ill, Obs. 45, pp. 271–272]—for once the margin was big enough!). The methods of this proof (see Weil [106, p. 77] or Edwards [31, pp. 10–14] for modem expositions) do not apply to our case, so that we are still in the dark. An analysis of Fermat’s approach to infinite descent appears in Bussotti [A5]. Weil’s book [106] makes a careful study of Fermat’s letters and marginal notes, and with some hints from Euler, he reconstructs some of Fermat’s proofs. Weil’s arguments are quite convincing, but we won’t go into them here. For the present, we prefer to leave things as Euler found them, i.e., wonderful theorems but no proofs.

B. Euler

Euler first heard of Fermat’s results through his correspondence with Goldbach. In fact, Goldbach’s first letter to Euler, written in December 1729, mentions Fermat’s conjecture that 22n + 1 is always prime [40, p. 10]. Shortly thereafter, Euler read some of Fermat’s letters that had been printed in Wallis’ Opera [100] (which included the one to Digby quoted above). Euler was intrigued by what he found. For example, writing to Goldbach in June 1730, Euler comments that Fermat’s four-square theorem (every positive integer is a sum of four or fewer squares) is a “non inelegans theorema” [40, p. 24]. For Euler, Fermat’s assertions were serious theorems deserving of proof, and finding the proofs became a life-long project. Euler’s first paper on number theory, written in 1732 at age 25, disproves Fermat’s claim about 22n + 1 by showing that 641 is a factor of 232 + 1 [33, Vol. II, pp. 1–5]. Euler’s interest in number theory continued unabated for the next 51 years—there was a steady stream of papers introducing many of the fundamental concepts of number theory, and even after his death in 1783, his papers continued to appear until 1830 (see [33, Vol. IV–V]). Weil’s book [106] gives a survey of Euler’s work on number theory (other references are Burkhardt [14], Edwards [31, Chapter 2], Scharlau and Opolka [86, Chapter 3], and the introductions to Volumes II–V of Euler’s collected works [33]).

We can now present Euler’s proof of the first of Fermat’s theorems from (1.1):

Theorem 1.2. An odd prime p can be written as x2 + y2 if and only if p ≡ 1 mod 4.

Proof. If p = x2 + y2, then congruences modulo 4 easily imply that p ≡ 1 mod 4. The hard work is proving the converse. We will give a modem version of Euler’s proof. Given an odd prime p, there are two basic steps to be proved:

It will soon become clear why we use the names “Descent” and “Reciprocity.”

We’ll do the Descent Step first since that’s what happened historically. The argument below is taken from a 1747 letter to Goldbach [40, pp. 416–419] (see also [33, Vol. II, pp. 295–327]). We begin with the classical identity

(1.3)

(see Exercise 1.1) which enables one to express composite numbers as sums of squares. The key observation is the following lemma:

Lemma 1.4. Suppose that N is a sum of two relatively prime squares, and that q = x2 + y2 is a prime divisor of N. Then N/q is also a sum of two relatively prime squares.

Proof. Write N = a2 + b2, where a and b are relatively prime. We also have q = x2 + y2 and thus q divides

Since q is prime, it divides one of these two factors, and changing the sign of a if necessary, we can assume that q|xb – ay. Thus xb – ay = dq for some integer d.

We claim that x | a + dy. Since x and y are relatively prime, this is equivalent to x | (a + dy)y. However,

which is obviously divisible by x. Furthermore, if we set a + dy = cx, then the above equation implies that b = dx + cy. Thus we have

(1.5)

Then, using (1.3), we obtain

Thus N/q = c2 + d2 is a sum of squares, and (1.5) shows that c and d must be relatively prime since a and b are. This proves the lemma. Q.E.D.

To complete the proof of the Descent Step, let p be an odd prime dividing N =...