[Mathematical Intelligencer 16 (1994), 67-72]
``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]
``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]
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' ''.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:
Hence
that is according as is even or odd. Hence our theorem follows at once [from Euler's Criterion that ].'' [11]
``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.
Let x be a non-integral quantity.
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.
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.
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:
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
Then
and the proof is complete.
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]