next up previous

Gauß, Eisenstein, and the ``third'' proof of the Quadratic Reciprocity Theorem: Ein kleines Schauspiel

Reinhard C. Laubenbacher - David J. Pengelley
Department of Mathematical Sciences
New Mexico State University
Las Cruces, NM 88003

[Mathematical Intelligencer 16 (1994), 67-72] gif

The year:
The characters:
Carl Friedrich Gauß , Director of the Göttingen Observatory, and the most prominent mathematician of the 19th century (and, possibly, of all time).
Gotthold Eisenstein, 21-year old mathematics student at the Friedrich-Wilhelms University in Berlin.
``Already early in my youth I was attracted by the beauty of a subject which differs from other subjects not only in its content but, most importantly, in the nature and variety of its methods. In it, it is not enough to just lay out the consequences of a single idea in a long sequence of deductions; almost each step requires one to conquer new difficulties and apply new principles.

A little over fifty years ago, number theory consisted only of a collection of isolated facts, unknown to most mathematicians, and practiced only occasionally by a few, even though Euler already found in it leisure from his other activities. It was through Gauß and some of his successors that number theory has reached such heights that now it is not inferior to any other mathematical discipline in depth and breadth, and has had a fruitful influence on many of them. A school has arisen which counts the most eminent mathematical talents among its disciples, and which I too proudly am a part of, if only one of its lowliest.'' [5]

Eisenstein (continuing):
You, Herr Direktor, have described so eloquently the strange attractions of this science, and have given several proofs of its Fundamental Theorem.
``The questions of higher arithmetic often present a remarkable characteristic which seldom appears in more general analysis, and increases the beauty of the former subject. While analytic investigations lead to the discovery of new truths only after the fundamental principles of the subject (which to a certain degree open the way to these truths) have been completely mastered; on the contrary in arithmetic the most elegant theorems frequently arise experimentally as the result of a more or less unexpected stroke of good fortune, while their proofs lie so deeply embedded in the darkness that they elude all attempts and defeat the sharpest inquiries. Further, the connection between arithmetical truths which at first glance seem of widely different nature, is so close that one not infrequently has the good fortune to find a proof (in an entirely unexpected way and by means of quite another inquiry) of a truth which one greatly desired and sought in vain in spite of much effort. These truths are frequently of such a nature that they may be arrived at by many distinct paths and that the first paths to be discovered are not always the shortest. It is therefore a great pleasure after one has fruitlessly pondered over a truth and has later been able to prove it in a round-about way to find at last the simplest and most natural way to its proof.

The theorem which we have called in sec. 4 of the Disquisitiones Arithemeticae the Fundamental Theorem, because it contains in itself all the theory of quadratic residues, holds a prominent position among the questions of which we have spoken in the preceding paragraph. We must consider Legendre as the discoverer of this very elegant theorem, although special cases of it had previously been discovered by the celebrated geometers Euler and Lagrange. I will not pause here to enumerate the attempts of these men to furnish a proof; those who are interested may read the above mentioned work. An account of my own trials will suffice to confirm the assertions of the preceding paragraph. I discovered this theorem independently in 1795 at a time when I was totally ignorant of what had been achieved in higher arithmetic, and consequently had not the slightest aid from the literature on the subject. For a whole year this theorem tormented me and absorbed my greatest efforts until at last I obtained a proof given in the fourth section of the above-mentioned work. Later I ran across three other proofs which were built on entirely different principles. One of these I have already given in the fifth section, the others, which do not compare with it in elegance, I have reserved for future publication. Although these proofs leave nothing to be desired as regards rigor, they are derived from sources much too remote, except perhaps the first, which however proceeds with laborious arguments and is overloaded with extended operations. I do not hesitate to say that until now a natural proof has not been produced. I leave it to the authorities to judge whether the following proof which I have recently been fortunate enough to discover deserves this description.'' [8,11]

Gauß (continuing):
The Quadratic Reciprocity Theorem compares the quadratic character of two primes with respect to each other. The quadratic character of q with respect to p is expressed by the Legendre symbol , defined to be 1 if q is a quadratic residue (i.e., a square) modulo p, and -1 if not.

Quadratic Reciprocity Theorem If p and q are distinct odd primes, then

 We also have the Ergänzungssatz

 for the prime 2.


Note that the theorem says that p and q have the same quadratic character with respect to each other if either one of them is  (mod 4), but not if both are  (mod 4).

Why is this theorem so important? First, it can be used to solve the general problem of when a quadratic congruence has a solution, since the Fundamental Theorem, along with the multiplicativity of the Legendre symbol, , enables one easily to compute its values, and thus to know exactly when square roots may be found modulo p. But it also represents an amazing and unexpected relationship between pairs of primes, a deep law governing prime numbers. Later in the century, Baumgart [2] will describe the role of the Fundamental Theorem within higher arithmetic:

``The higher arithmetic in essence divides into two main parts, the theory of congruences and the theory of homogeneous forms. The theory of binomial congruences forms an integrating part of the general theory of congruences. `The reciprocity laws are the cornerstone of the latter theory' gif''.
In my lifetime I will in fact present eight different proofs of the Fundamental Theorem, and other mathematicians will find many more. But my third published proof, which I will now present, is perhaps the most natural one I know. My proof begins with a theorem which in the future might be called

Gauß ' Lemma Let p be prime, and q any number not divisible by p. Then

 with  obtained as follows: Let

 Then  is defined to be the number of least positive residues modulo p of the set  which lie in .

``Proof: Let  be the residues belonging to the class  and  be those belonging to . Then it is clear that the complements of the latter,  are not equal to any of the numbers  [for if, say,  where x,y come from  , then  would be divisible by p, which cannot occur since both x and y lie strictly between 0 and , and together with them make up the class . Consequently we have

 The right-hand product evidently becomes, modulo p:



 that is  according as  is even or odd. Hence our theorem follows at once [from Euler's Criterion that ].'' [11]

Hochgeehrtester Herr Hofrath, I too have devoted much effort to the study of the quadratic reciprocity law and have given four different proofs of it. My recently published geometric proof [7] is related to your third proof and, with all due modesty, represents something of an improvement in the exposition of the main ideas underlying it. My excitement is clear in the letter I wrote to my friend Moritz Stern in Göttingen:
``I did not rest until I freed my geometric proof, which delighted you so much, and which also, incidentally, particularly pleased Jacobi, from the Lemma [of Gauß ] on which it still depended, and it is now so simple that it can be communicated in a couple of lines. The main difference between my argument and that of Gauß is that I do not divide the numbers less than p into those less than  and those greater than , but rather into even and odd ones.'' [9]
Instead, I begin my proof as follows, with what may hopefully someday be called Eisenstein's Lemma. Consider the set . Let r denote the remainder (mod p) of an arbitrary multiple qa. Then it is apparent that the list of numbers  agrees with the list of numbers , up to multiples of p. (For clearly each of the numbers  has even least positive residue, and if there were duplication among these residues, e.g.

 then . Since the a's are distinct, it follows that , which cannot occur since  and  is even.) Thus

 from which it follows that  (mod p). Recalling Euler's Criterion that  (mod p), this produces


 so one may focus solely on the parity of the exponent. This formula is my replacement for your Lemma. Because the exponent is algebraic in nature, my proof will now proceed more easily than yours. Incidentally, the odd terms actually contributing to the parity of this exponent correspond exactly to the ones counted in your Lemma.

Well, we shall see about that, Herr Student. I will begin the main part of my proof by deriving a few technical facts about the greatest integer function  which are needed subsequently.

Let x be a non-integral quantity.

  1. , whenever b is an integer.
  2. If  is a fraction less than , then . If on the other hand  is greater than , then . Thus:
  3. If the smallest positive residue of b (mod p) is less than , then . If, however it is larger than , then .
  4. From this it follows that

But with all due respect, Herr Hofrath, the formula ( 1) in my Lemma already produces the essence of this more quickly and transparently. Clearly

 Since the elements a are all even, and p is odd, it follows that  and thus from (1) that


 This is equivalent to what you have learned about  in (2), since only the parity is relevant.

Well, Herr Eisenstein, that was indeed a clever shortcut to formula (3), leading now to the following necessary calculations. I transform the formula (2) as follows: From property 1 above, we have


When we apply these substitutions to the last terms of the top series in (2) we have:

first, when p is of the form 4n+1,


second, when p is of the form 4n+3,


From these the Ergänzungssatz follows for q=2, and we assume henceforth that q is an odd prime.


 Herr Direktor, the Ergänzungssatz also follows easily from my (3 ). And, secondly, the results of your substitutions can all be interpreted geometrically for q odd. Let us use a simple geometric representation of the exponent  in (3) to transform it while retaining its parity: This exponent is precisely the number of integer lattice points with even abscissas lying in the interior of triangle ABD in the Figure (note that no lattice points lie on the line AB). Consider an even abscissa . Since the number of lattice points on each abscissa in the interior of rectangle ADBF is q-1, which is even, the number of lattice points on the abscissa below AB has the same parity as the number of lattice points above AB. This in turn is the same as the number of points lying below AB on the odd abscissa p-a. This one-to-one correspondence between even abscissas in triangle BHJ and odd abscissas in AHK now implies that  where  is the number of points inside triangle AHK, and thus

 In each of your expressions above for , the first line is even, and the second line counts precisely the lattice points in triangle AHK. Your substitutions are realized simply by these geometric transformations when we focus specifically on the parity.

Gauß (aside):
Darn, my calculations really do seem clumsy compared with this youngster's geometric methods.
Gauß (to Eisenstein again):
Very well Herr Eisenstein, there does seem to be some merit to your approach. But now your geometry has reached its limit, and we must compare the reciprocal roles of p and q as follows.

Considering the second line in each of the expressions above for , and comparing it with the same expression when the roles of p and q are interchanged, I will prove that

 This is somewhat technical and lengthy, but we begin as follows: 

Eisenstein (agitated):
But Herr Hofrath, please, this is immediately obvious from the geometric representation, for it is merely the sum of the number of lattice points  in triangle AHK with the number  in triangle AHL, which clearly equals the total number  inside the rectangle.
Gauß (after some hesitation):
Indeed, verehrter Herr Eisenstein, this is impressive! For the sake of completeness, though, I will now finish my argument by letting

 where  has the same definition as  does but with the roles of p and q interchanged. Then from the expressions above for  we see that L, and likewise M, are even, and moreover


 and the proof is complete.

Herr Hofrath, thank you for your kind words. Of course my proof was already finished before, since I have


As I wrote to my friend Stern,

``How lucky good Euler would have considered himself, had he possessed these lines about seventy years ago.'' [9]
Eisenstein (aside):
I wonder if Gauß already had my geometric view of his transformations when he published his third proof in 1808, and if the old fox has merely been humoring me all along in our conversation.

next up previous

To main page on
Teaching with Original Historical Sources in Mathematics

D. Pengelley and R. Laubenbacher

Thu Feb 11 17:12:00 MST 1999