[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]
,
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'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: Letbe 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 thanInstead, I begin my proof as follows, with what may hopefully someday be called Eisenstein's Lemma. Consider the setand those greater than
, but rather into even and odd ones.'' [9]
.
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.
which are needed
subsequently.Let x be a non-integral quantity.
, whenever b is an integer.
is a fraction less than 
,
then 
. If on the other hand 
is greater than 
, then 
.
Thus:
,
then 
. If, however it is
larger than 
, then 
.
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: 
in triangle AHK with the number 
in triangle AHL, which clearly equals the total number 
inside the rectangle.
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]
