The Prince of Mathematicians



The Law of Quadratic Reciprocity

Proof: By Wilson’s Theorem

By Kylee Bracher

Portland State University

Department of Mathematics and Statistics

Summer, 2005

In partial fulfillment of the Masters of Science in Mathematics

Advisors:

John Caughman

Steve Bleiler

Table of Contents

1. Introduction and History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2. Preliminary Definitions, Theorems and Examples . . . . . . . . . . . . . . . . . . . . . . . 3

3. The Law of Quadratic Reciprocity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16

4. Geometric Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22

5. Schmidt’s Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

1. Introduction and History

One of the high points in all of elementary number theory is the Law of Quadratic Reciprocity which was first proven by Carl Friedrich Gauss on April 8, 1796 and published in his work Disquisitiones Arithmeticae.

Throughout Gauss’s life he had a particular passion for “higher arithmetic” which we know today as number theory. This is evident by his own authoritative statement that, “Mathematics is the queen of the sciences, and higher arithmetic, the queen of mathematics.” “Gauss’s Law of Quadratic Reciprocity which he called the “Golden Theorem of Number Theory” is one of the gems of eighteenth and nineteenth century mathematics.” (Beach and Blair, 265) The first statement of a theorem equivalent to this law was found in the works of Euler without proof in the period 1744-1746. The result was then rediscovered in 1785 by Adrien-Marie Legendre, who provided two proofs that he believed to be complete but which later turned out to be invalid. In his first attempt at a proof he assumed that for any prime p congruent to 1 modulo 8, there exists another prime q congruent to 3 modulo 4 for which q is a quadratic residue, a result which is as difficult to prove as the law itself. “He attempted another proof in his Essai sur la Theorie des Nombres (1798); this one too contained a gap, since Legendre took for granted that there are an infinite number of primes in certain arithmetical progressions (a fact eventually proved by Dirichlet in 1837, using in the process very subtle arguments from complex variable theory). (Burton, 235) In 1795, Gauss discovered the result independently at the age of 18, and a year later provided the first complete proof. Gauss kept returning to the Law of Quadratic Reciprocity, searching for proofs that would generalize to higher reciprocity laws.

In all, Gauss published six proofs and no doubt discovered several others. He was fully aware of its central importance and the role it would play in the further development of number theory. Leopold Kronecker later referred to its proof as the “test of strength of Gauss’ genius.”

To date there are over 200 known proofs of the Law of Quadratic Reciprocity. This paper will explore two of these proofs. The first is a geometrical interpretation of one of Gauss’s proofs. This proof is very visual and relies very heavily on what is known today as Gauss’s Lemma. The second proof was found in an article by Hermann Schmidt published in 1839 entitled Drei neue Beweise des Reciprocitatssatzes in der Theorie der quadraischen (“Three New Proofs of the Theory of Quadratic Reciprocity) , which is in turn a variant of the fifth proof by Gauss. As is known, Euler’s Criterion and the theorems of Fermat and Wilson can be proved in a very simple manner by determining in two ways a product. Schmidt shows that the same is true for the Law of Quadratic Reciprocity. “The noteworthy feature of Schmidt’s proof is that is dispenses with Gauss’s Lemma and depends on nothing more mysterious than the Chinese Remainder Theorem and Wilson’s Theorem.” (Rousseau, 424)

2. Preliminary Definitions, Theorems, and Examples

Before we begin an examination of the Law of Quadratic Reciprocity we must first define some terms and theorems that will be used throughout the discussion. We will assume that the reader is familiar with some of the more elementary concepts in Number Theory such as primes, relatively prime, Division Algorithm, Euclidean Algorithm, and the Greatest Integer function. The reader may refer to Burton’s Elementary Number Theory text as a reference for these and other elementary concepts. Readers which are already familiar with Quadratic Reciprocity may want to skip to the Geometric Proof section of this paper.

Definition 1: (Congruence) Let n be a positive integer. Integers a and b are said to be congruent modulo n, denoted by [pic] if they have the same remainder when divided by n.

Lemma 1: Let a, b, and n > 0 be integers. Then [pic]if and only if [pic]

Proof: [pic] If[pic], then by definition a and b have the same remainder when divided by n, so by the division algorithm a = nk + r and b = nm + r for some integers k, m, and r with[pic]. Now if we solve both of these equations for r we have

[pic]

[pic] [pic]

[pic]

If [pic]then [pic] which is what we wanted to show.

[pic] Now assume that[pic]. By the division algorithm there exists integers k and m such that, a = nk + [pic] and b = nm + [pic], where [pic] and[pic]. Subtracting b from a we obtain the equation[pic], and since it was assumed [pic], it must be that [pic]. But [pic] and so [pic] and the only multiple of n in this interval is 0. Thus we have that [pic] or equivalently [pic], and so [pic] which is what we wanted to show. ▲

The reader may think that we do not need a new and slightly longer way to say[pic]. However the notation[pic]is useful because it suggests an equation, and in fact congruences share many properties with equations. The next couple of theorems list a number of ways in which congruences behave like equations.

Theorem 1: (Basic Properties for Congruences: Let p > 0 be a fixed integer and a, b, c, and d be arbitrary integers. Then the following properties hold:

(1) [pic].

(2) If [pic], then [pic].

(3) If [pic] and [pic], then [pic].

(4) If [pic]and [pic], then [pic] and

[pic].

(5) If [pic], then [pic]and [pic].

(6) If [pic], then [pic]for any positive integer k.

Theorem 2: (Cancellation Law): If a is relatively prime to p and x and y are integers such that [pic], then[pic]

Proof: By definition [pic] means p divides [pic]. Given that a and p are relatively prime p must divide (x – y) since the prime factorization is unique by the Fundamental Theorem of Arithmetic. If p divides (x – y) then by definition[pic] which is what we wanted to show. ▲

Definition 2: (Least Residue): If n > 0 and r is the remainder when the Division Algorithm is used to divide b by n, then r is called the least residue of b modulo n.

Examples: The least residue of 13 modulo 5 is 3. The least residue of 5 modulo 13 is 5. The least residue of -13 modulo 5 is 2. The least residue of – 2 modulo 3 is 1. ▲

Lemma 2: If a is relatively prime to p, p > 0, then there exists a unique integer x modulo n such that [pic]

Proof: Let (a, n) = 1 then by the Euclidean Algorithm we can write 1 as a linear combination of a and n, that is, [pic]for some integers x and y. Rearranging the terms in this equation we have [pic]. Hence [pic]which implies that [pic]by the definition of congruence.

To prove uniqueness, suppose that [pic]and [pic]. Then

[pic]

[pic] [pic]

[pic] [pic]

[pic] [pic] (since (a, n) = 1)

By definition of congruence if [pic] then [pic]. Therefore the solution x must be unique modulo n. ▲

Definition 3: Let a be any integer. Any integer x for which [pic]is called the inverse of a.

Definition 4: Let n be a positive integer, and let a be an integer such that[pic] Then a is called a quadratic residue modulo n if the congruence

[pic][pic]

is solvable, and a quadratic nonresidue otherwise.

Definition 5: (The Legendre Symbol): Suppose p is an odd prime not dividing a. We define the symbol [pic] to be 1 or – 1 according to whether a is a quadratic residue or quadratic nonresidue mod p. This is called the Legendre Symbol, after the French mathematician Adrien Marie Legendre (1752 – 1833). We also call [pic] the quadratic character of a with respect to p.

If [pic] then a is a quadratic residue modulo p which means the congruence[pic] is solvable. In fact, if a is a quadratic residue modulo p then the congruence has exactly two solutions modulo p. This fact is verified through the following theorem and proposition.

Theorem 3: (Lagrange’s Theorem): If p is a prime and

[pic] [pic]

is a polynomial of degree [pic] with integral coefficients, then the congruence

[pic]

has at most n incongruent solutions modulo p.

Proof: See Burton page 191. ▲

Proposition 1: Let p be an odd prime and a be any integer such that [pic] If the congruence [pic]is solvable, then there are exactly two incongruent solutions modulo p.

Proof: Suppose that the congruence [pic]is solvable and let [pic] be one of the solutions. Note [pic] since [pic] Then there must also be a second solution [pic] since [pic] and [pic]. This second solution is not congruent to the first. To see this, note that [pic] implies that [pic] or equivalently[pic] which is impossible. Now by Lagrange’s Theorem, these two solutions exhaust the incongruent solutions of [pic]. Thus, if [pic]is solvable there are exactly two incongruent solutions modulo p. ▲

For the remainder of this paper we will always assume that p is an odd prime such that a is not divisible by p. Next we will look at an example that incorporates all of the previous definitions.

Example 1: When a = 3 and p = 11, the quadratic character of 3 with respect to 11 is equal to 1, or [pic], because there exists an x such that [pic]is solvable. To find x we simply square the numbers from 1 to 10, subtract 3, and see if the result is divisible by 11. Thus we have that

[pic] not divisible by 11

[pic] not divisible by 11

[pic] not divisible by 11

[pic] not divisible by 11

[pic] divisible by 11. Thus, [pic]is a solution.

[pic] divisible by 11. So, [pic]is also a solution.

Recall by Proposition 1 that if a is a quadratic residue modulo p, then the congruence has exactly two solutions. Thus, we can stop here. We should also note, [pic]. So we could write that the solutions to the congruence [pic] are exactly[pic]. It is easy to see that this fact is true since,

[pic] [pic] [pic] [pic] [pic]

is clearly true. A similar argument would show that the congruence holds for[pic].

Now it is a little deceptive to say that there are only two solutions to the congruence because actually there are infinitely many solutions. It just happens that any other solution will be congruent to [pic]. For example, 16 is also a solution to the congruence since

[pic] [pic] [pic] [pic] [pic]

This statement is true because 253 = (23)(11). Similarly 27, 38, 49, . . . . . , 5 + 11k where k is any integer, are all solutions to the congruence [pic]. The integers -16, -27, -38, . . . . . . . , - 5 – 11k where k is any integer are also solutions because each of these integers are congruent to [pic]. ▲

The quadratic residues for a system can be found by squaring the numbers from 1 to p – 1 and reducing them modulo p as we will see in the following example.

Example 2: When p = 11, the quadratic residues can be found by squaring the numbers from 1 to 10 and reducing them modulo 11.

Squaring the numbers from 1 to 5 yields:

[pic]

Squaring the numbers from 6 to 10 yields the same residues in reverse order:

[pic]

So the quadratic residues mod 11 are 1, 3, 4, 5, 9 and the quadratic nonresidues are 2, 6, 7, 8, 10. ▲

Since the numbers from 1 to [pic] yield the same residues as the numbers from [pic] to p, the quadratic residues can be found simply by squaring the numbers from 1 to [pic].

Theorem 4: Let p be an odd prime. Then half of the numbers between 1 and p – 1 are quadratic residues of p, and half are nonresidues.

Proof: Any quadratic residue of p must be congruent modulo p to one of the numbers [pic]as was illustrated in the example above. Note that [pic] So the squares of the numbers from [pic] up to p – 1 are congruent to the squares of the numbers [pic] down to 1.

All we have left to show is that each of the squares of [pic] is not congruent to any one of the other squares. We will do this by contradiction.

Suppose that there exist two squares such that [pic] where i and j are distinct and both in the range 1 to [pic] Then

[pic]

[pic] or [pic]

These last two statements are always false because both i and j lie within the range [pic] Thus, i – j and i + j are both too small to be divisible by p. So we have shown that none of the squares are congruent mod p. Thus, there must be exactly [pic] quadratic residues of p. ▲

In general, the above theorem says that there are exactly [pic] quadratic residues and exactly [pic] nonresidues of p.

The last theorem in this section, Euler’s Criterion, will be used throughout the discussion of both proofs of the Law of Quadratic Reciprocity presented in the sections Geometric Proof and Schmidt’s Proof below. In order to appropriately discuss the proof of Euler’s Criterion we must first look at a preceding theorem known as Fermat’s Little Theorem.

Theorem 5: (Fermat’s Little Theorem): Let p be any prime number. If a is any integer such that [pic]then [pic]

Proof: Consider the set P = {1a, 2a, 3a, . . . . . . . , (p – 1)a}. By the Cancellation Law each of these numbers must be distinct modulo p. So modulo p, the set P is the same as the set of integers N = {1, 2, 3, . . . . . . . , (p – 1)}. So if we multiply the elements of these two sets together, we would get the same result modulo p, that is,

[pic]

Regrouping the left hand side we obtain:

[pic]

or equivalently

[pic]

To finish the proof we need only to cancel the common term of (p – 1)! from both sides. Given that p is prime, p and (p – 1)! can have no factors in common. Thus by the previous lemma we can divide both sides by (p – 1)! yielding [pic] which is what we wanted to show. ▲

Theorem 6: (Euler’s Criterion): Let p be an odd prime and a any integer such that[pic]. Then a is a quadratic residue modulo p if and only if [pic]

Proof: [pic]Let a be a quadratic residue modulo p. Then there must exist an x such that [pic]. Since it was assumed that [pic] this implies [pic] Thus by Fermat’s Little Theorem we have

[pic]

Hence if a is a quadratic residue modulo p then [pic]which is what we wanted to show.

Recall that if (r, p) = 1 and r has order[pic]modulo p (where[pic]is the largest possible order), then r is called a primitive root of p.

[pic] Now suppose that the congruence [pic]holds and let r be a primitive root of p, r exists because p is assumed to prime. If r is a primitive root of p then [pic] for some integer m, with [pic] Thus it follows that

[pic]

Given that r is a primitive root of p the order of r is p – 1. By the previous congruence [pic]so p – 1 must divide m(p – 1)/2 which implies that m must be an even integer. Let m = 2k, then [pic]

making the integer [pic]a solution of the congruence [pic] Thus a is a quadratic residue modulo p which is what we wanted to show. ▲

Example 4: Let a = 17. For which primes p is 17 a quadratic residue? We can test prime p's manually given the formula above.

If we let p = 3, we have 17(3 − 1)/2 = 171 ≡ 2 (mod 3) ≡ -1 (mod 3), therefore 17 is not a quadratic residue modulo 3.

Now if we let p = 13, we have 17(13 − 1)/2 = 176 ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 22 = 4. ▲

The following results are direct consequences of Euler’s Criterion.

Lemma 3: The congruence [pic]is solvable if and only if [pic]

Proof: By Euler’s Criterion, [pic]is solvable if and only if [pic]. But [pic] is either 1 or -1 depending on whether (p – 1)/2 is even or odd, respectively. Since p > 2, [pic]if and only if (p – 1)/2 is even. But (p – 1)/2 is even if and only if [pic] which is what we wanted to show. ▲

Example 5: When p = 17, the congruence [pic]is solvable since [pic]. The solutions to the congruence [pic]are exactly [pic]. ▲

Corollary 1: Let [pic] be an odd prime and a any integer such that[pic]. Then a is a quadratic residue modulo p if and only – a is a quadratic nonresidue modulo p.

Proof: [pic] Let a be a quadratic residue modulo p. By Euler’s Criterion, if a is a quadratic residue modulo p then [pic] So to show that –a is a quadratic nonresidue we need only show that [pic] But

[pic]

since (p – 1)/2 is odd. Hence – a is a quadratic nonresidue modulo p, which is what we wanted to show.

[pic] Let –a be a quadratic residue modulo p. By Euler’s Criterion, if –a is a quadratic residue modulo p then [pic] So to show that a is a quadratic nonresidue we need only show that [pic] But

[pic]

since (p – 1)/2 is odd. Hence a is a quadratic nonresidue modulo p, which is what we wanted to show. ▲

Corollary 2: Let [pic] be an odd prime and a any integer such that[pic]. Then a and –a are either both quadratic residues modulo p or quadratic nonresidues modulo p.

Proof: First we will assume that a be a quadratic residues modulo p. By Euler’s Criterion, if a is a quadratic residue modulo p then [pic] So to show that –a is a quadratic residue modulo p we need only show that [pic] But

[pic]

since (p – 1)/2 is even. Hence –a is a quadratic residue modulo p.

Now assume that a is a quadratic nonresidue modulo p. Then by Euler’s Criterion, [pic] To Show that –a is also a quadratic nonresidue modulo p we need only show that [pic] But

[pic]

since (p – 1)/2 is even. Hence –a is a quadratic nonresidue modulo p, which is what we wanted to show. ▲

3. The Law of Quadratic Reciprocity

We are now ready to present the statement of the Law of Quadratic Reciprocity.

Law of Quadratic Reciprocity: Let p and q be distinct odd primes. Then

[pic].

We should remark that by the statement of the Law of Quadratic Reciprocity [pic] if [pic]or[pic], while [pic] if [pic].

Before we look at how we can actually prove this statement we will first look at a few examples which illustrate the different ways in which the Law of Quadratic Reciprocity may be used.

Example 6: Let p = 3 and q = 17 then [pic] which is what is expected since q = 17 is of the form 4k + 1. Thus by the Law of Quadratic Reciprocity the congruences

[pic] and [pic]

are either both solvable or both insolvable. The easiest congruence to check would be [pic] since it reduces to the congruence [pic] which is clearly not solvable since [pic] and [pic] are not divisible by 3. Therefore both of the congruences are insolvable and so [pic] and[pic]. ▲

The following examples illustrate how you can use the Law of Quadratic Reciprocity to determine the quadratic character of p with respect to q, when the value of either p or q is known.

Example 7: In this example we will determine the value of the quadratic character of 7 with respect to p when p is an odd prime different from 7. We should note that 7 is an odd prime of the form 4k + 3 (since 7 = 4(1) + 3). Now by the Law of Quadratic Reciprocity we have

[pic]

To determine the value of [pic]we must consider two things:

1) The value of [pic];

2) The value of the exponent on -1.

To find the value of [pic] we can find the least residues modulo 7 squaring the numbers from 1 to 3[pic] and reducing them mod 7. Squaring the numbers from 1 to 3 yields [pic]. Thus, the quadratic residues mod 7 are 1, 2, 4 and the quadratic nonresidues are 3, 5, 6.

Now with the previous work done we can determine the value of [pic] for each value of a from 1 to 6.

If[pic], then[pic] since 1 is a quadratic residue mod 7.

If[pic], then[pic] since 2 is a quadratic residue mod 7.

If[pic], then[pic] since 3 is a quadratic nonresidue mod 7.

If[pic], then[pic] since 4 is a quadratic residue mod 7.

If[pic], then[pic] since 5 is a quadratic nonresidue mod 7.

If[pic], then[pic] since 6 is a quadratic nonresidue mod 7.

Next we must note that since p is an odd prime then p is either of the form

4k + 1 or 4k + 3.

Case 1) p = 4k + 1 where k is any integer

[pic]

If [pic], then the exponent on -1 is

[pic] an even number.

Case 2) p = 4k + 3 where k is any integer

[pic]

If [pic], then the exponent on -1 is

[pic] an odd number.

The assumptions on p show that it is not divisible by 7 because we assumed that p was odd prime different from 7 and it is not divisible by 4 because it either has a remainder of 1 or 3 when divided by 4. Thus, p must be relatively prime to their product (7)(4) = 28. So p must be congruent to one of 1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, or 27 (all numbers between 1 and 28 that are relatively prime to 28). If [pic], then

28 | (p – 1)

[pic]

[pic] and [pic]

[pic] and [pic]

[pic] the exponent on -1 is even so [pic]

[pic].

Hence the value of the Legendre symbol is [pic]

This example illustrates how when one of the odd primes is of the form

4k + 1, then either both of the congruences are solvable or both are unsolvable, yielding the same quadratic characters for [pic]and[pic] In this case, they are both solvable since

[pic]

Next we will illustrate the case when both p and q are of the form 4k + 3, if[pic]then

[pic]

[pic]

[pic] and [pic]

[pic] and [pic]

[pic]the exponent -1 is odd so [pic]

[pic] (since 3 is a quadratic residue mod 7)

Hence the value of the Legendre symbol for [pic]

In this example the value of the quadratic characters for [pic]and[pic]are opposite, so one of the congruences is solvable and one is not. You could continue in this fashion checking all of the values 1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, and 27. The results are summarized below.

1 if [pic]

[pic]= -1 if [pic]

From this it is easy to see that if for example p = 27 then [pic] Thus, there must exist an x such that [pic]is solvable. After checking the values from 1 to 27 it can be easily be verified that [pic]are the solutions to the congruence since

[pic]

which is clearly true since 162 = (27)(6). ▲

Example 8: What about for larger values of p? Suppose that p = 1,999 and q = 3. Both are of the form 4k + 3 so by The Law of Quadratic Reciprocity of the congruences [pic]and [pic]only one is solvable. The first congruence [pic]reduces to [pic] since 1,999 is congruent to 1 mod 3.

[pic] is clearly solvable when [pic]since

[pic] [pic] [pic] [pic]

Therefore, by the Law of Quadratic Reciprocity the second congruence [pic]must have no solution. You could verify that this congruence has no solution by testing each of the numbers from 1 to 999, but the Law of Quadratic Reciprocity solves the problem without any need for testing.

Now let’s look at a case where one of the numbers p or q is of the form 4k + 1. Suppose that p = 1,999 and q = 5. Then the law states that the congruences [pic] and [pic] are either both solvable or unsolvable. The first congruence [pic] reduces to [pic] since 1,999 is congruent to 4 mod 5. The congruence [pic]is clearly solvable when [pic] since

[pic] [pic] [pic] [pic].

By the Law of Quadratic Reciprocity the other congruence [pic] must also be solvable. In order to determine the solution by brute force we would have to square the numbers between 1 and 999. It turns out that there is another method for finding the solution without squaring all of the numbers from 1 to [pic] If p is of the form 4k + 3 (which in this case it is, [pic] then one solution is [pic] So for this particular example the congruence [pic] has the solution [pic] With the help of a calculator it can be checked that this yields [pic], so the other answer is [pic]. ▲

There are several other uses of Quadratic Reciprocity that may found in many textbooks. The reader may want to refer to Burton’s text, Elementary Number Theory, for further illustrations.

4. Geometric Proof

The geometric interpretation of Gauss’s proof of the Law of Quadratic Reciprocity relies very heavily on what is known today as Gauss’s Lemma. So before we begin our exploration of this proof we will first introduce and discuss this concept.

Lemma 4: Gauss’s Lemma: Let p be an odd prime and a an integer not divisible by p. Consider the least residues of the integers ka for [pic], reduced to lie between [pic] to [pic]. If the number of these which are negative is s, then[pic].

Proof: Let the least residues be [pic] for [pic] and [pic] for [pic] where [pic] [pic], and [pic] We first claim, with proof to follow, that the set[pic] Given that this is true we have

[pic]

if we divide both sides by [pic] we are left with

[pic].

Now by Euler’s Criterion[pic]. Thus we have that[pic].

Given that [pic] and [pic]will both yield values of either 1 or -1, it follows that [pic] (since p is prime) which is what we wanted to show.

Thus, all we need is to prove the claim that the set of least residues disregarding signs is exactly equal to the set of integers from 1 to [pic]or equivalently [pic] To do this we must show that no two [pic] are congruent, no two [pic]are congruent and that there are no [pic] We will do this by contradiction.

Let’s assume that two [pic] are congruent then [pic]with [pic] and assuming without loss of generality that [pic] (if [pic] we would be talking about the same element in the set).

[pic]

[pic] (since [pic]

This last statement is always false because both [pic] and [pic] fall within the range [pic] So [pic] Thus, [pic] is too small to be divisible by p.

Next we assume that two [pic] are congruent then [pic] with [pic] Now

[pic]

[pic] (since [pic]

This last statement is again false by the same reasoning as above.

Finally, we will assume that [pic] for some[pic][pic], then [pic] for some [pic] So

[pic]

[pic] (since [pic]

This last statement is also false because again both [pic] and [pic] fall with the range [pic] So [pic] Clearly no integer within this range is divisible by p.

Thus, we have shown that no two integers in the set [pic] are congruent to one another and since there are exactly[pic] elements in this set, each within the range 1, . . . . , [pic], it must be that[pic] Which is what we wanted to show. ▲

Example 9: Take p = 11 and a = 19, we first reduce each 19k for [pic]mod 11 to lie within the range [pic] to[pic]. Thus, we get

for k = 1, [pic]

for k = 2, [pic]

for k = 3, [pic]

for k = 4, [pic]

for k = 5, [pic]

So the least residues for the first 5 multiples of 19 modulo 11 are -1, 2, -3, -4, 5, which we should note are exactly the integers from 1 to[pic]. From the chart above we see there are 3 minus signs, so by Gauss’s Lemma[pic]. So 19 is a quadratic nonresidue mod11. Thus there does not exist an x such that[pic]. ▲

In this next example we will just reverse the roles of 19 and 11.

Example 10: Now let p = 19 and a = 11, we first reduce each 11k for [pic]mod 11 to lie within the range [pic] to [pic]. Thus, we get

for k = 1, [pic]

for k = 2, [pic]

for k = 3, [pic]

for k = 4, [pic]

for k = 5, [pic]

for k = 6, [pic]

for k = 7, [pic]

for k = 8, [pic]

for k = 9, [pic]

So the least residues for the first 9 multiples of 11 modulo 19 are 1, -2, 3, 4, -5, 6, -7, -8, 9, which in this case are exactly the set of integers from 1 to [pic]. From the chart above we see that there are 4 minus signs, so by Gauss’s Lemma [pic]. In this case, 11 is a quadratic residue mod 19. Thus, the congruence[pic]is solvable. In fact, the solutions to this congruence are exactly[pic] since

[pic] [pic] [pic] [pic] 19 | 38

which is clearly true. A similar argument would hold for [pic] ▲

We are now ready to look at the geometric interpretation of Gauss’s proof. The following proof is based on a proof presented in the The Jewel of Arithmetic: Quadratic Reciprocity found online at .

Proof of the Law of Quadratic Reciprocity: A point in the x, y plane will be called a lattice point if both its coordinates are integers. We will count lattice points in various regions.

Consider the rectangle R in the x, y plane with sides y = 1 and [pic] and vertical sides x = 1 and [pic] The total number of lattice points in or on the rectangle is equal to [pic] (exactly equal to the exponent on (-1) in the statement of the theorem). This is illustrated in the graph below where p = 11 and q = 19, in this case there are [pic]lattice points in the rectangle.

Figure 1

[pic]

Next we will use three lines to divide the rectangle into four regions. Let

L be the line[pic] (or x = [pic])

[pic] be the line [pic]

[pic] be the line [pic] (or [pic])

Figure 2

[pic]

We should note that there are no lattice points on any of these lines within the rectangle because [pic] and [pic] since all of the coordinates x within the rectangle are in the range [pic] and all of the coordinates y are in the range [pic]

We will let A be the region above [pic] where [pic]

B be the region below [pic] where [pic]

[pic] be the region between L and [pic] where [pic]

[pic] be the region between L and [pic] where [pic]

This again is illustrated in the graph below for the case when p = 11 and q = 19.

Figure 3

[pic]

If we let P(X) denote the number of lattice points in region X it should be that

P(A) + P(B) + P([pic]) + P([pic]) = [pic]

Thus, the statement of the theorem could be written in the form

[pic]

We will first show that A and B contain the same number of lattice points so the sum of P(A) and P(B) will always be even. Thus, they will have no effect on the exponent of (-1). So the statement of the theorem can be reduced to the following expression

[pic]

We will then show that [pic] contains [pic] points where [pic] and that [pic] contains[pic] where[pic]. So we could again restate the theorem as

[pic]

where,[pic].

To see that P(A) = P(B) note that the entire picture is symmetric about its center point [pic] as illustrated in the graph below.

Figure 4

[pic]

To verify this claim, let f : [pic] be defined by [pic] with the property that [pic] We will show that this mapping f is a one-one correspondence between the lattice points of A and those in B.

Proof: To prove that f is a one-one correspondence between the lattice points of A and B we must show that f is a one-one and onto mapping between the lattice points of A and B.

We must first verify that f maps the lattice points of A to the lattice points in B. Let[pic] be any lattice point in A, then x and y are both integer values such that [pic]. We wish to show that [pic] is a lattice point in B. Observe first that f (x, y) will be a lattice point since both p and q were assumed to be odd. By the definitions of regions A and B, the reader can easily check that if [pic] then [pic] . Hence[pic], which is what we wanted to show.

To show that f is one-one we must show that f(a, b) = f (c, d) implies that (a, b) = (c, d). Now,

[pic]

[pic]

[pic] and [pic]

[pic] and b = d

[pic]

which is what we wanted to show. Therefore, f is one-one.

Next we must show that f is onto. To show that f is onto we must show for each [pic] there exists an[pic]such that [pic] Suppose [pic] and let[pic], then (x, y) [pic]since by definition of the region B [pic] and thus the reader can easily verify through algebra that this implies that [pic]. Hence (x, y) [pic] and (x, y) is clearly a lattice point since p and q were assumed to be odd. Further,

f (x, y)

[pic]

Thus, there exists a lattice point [pic], namely[pic], such that

[pic] Therefore, f is onto. We have shown that f is one-one and onto. Therefore, we have shown that f is a one-one correspondence between the lattice points of A and those of B. Hence, P(A) = P(B).

Next we will examine the number of lattice points in [pic] Let [pic] Then [pic] if and only if [pic] by definition of the region [pic] The interval has length [pic] so it contains at most one integer y. There will be an integer y in this interval if and only if there is an integer [pic] (where [pic]denotes the greatest integer) in the interval

[pic]

which is if and only if

[pic]

Multiplying through by p we get the equivalent statement

[pic].

The integer in the middle is the remainder on dividing qx by p. The number of x’s in the range [pic] for which the remainder lies between [pic] and p is exactly the same integer s which occurs in Gauss’s Lemma satisfying [pic] A similar argument could be used to show that the number of lattice points in [pic]is the integer [pic] which appears in Gauss’s Lemma such that [pic] Thus we have, [pic]

which is exactly what we wanted to show. ▲

Example 11 (for p = 11 and q = 19): We should note that p and q are both of the form 4k + 3. Thus, we must show that

[pic]

We will proceed by counting lattice points in various regions. Consider the

rectangular region R in the x, y plane with sides y = 1 and [pic] and vertical sides x = 1 and [pic]. The total number of lattice points in or on the rectangle is equal to[pic], as illustrated in the graph below.

Figure 5

[pic]

Next we will use three lines to divide the rectangle into four regions. We will let

[pic] be the line [pic]

[pic]be the line [pic]

[pic]be the line [pic] [pic]

We should note that no lattice points lie on any of these lines within the rectangle because [pic] when [pic]and similarly [pic] when[pic].

We will let

A be the region above [pic] where [pic]

B be the region above [pic] where [pic]

[pic]be the region between L and [pic] where [pic]

[pic]be the region between L and [pic] where [pic]

Figure 6

[pic]

If we let P(X) denote the number of lattice points in Region X, it should be that,

[pic]

Thus, the statement of the theorem could be rewritten as

[pic]

One could use a rigorous algebraic proof to show that the number P(A) = P(B). However, for the purpose of this discussion we will use the graph to illustrate this idea.

Figure 7

[pic]

It is obvious from the graph that if you were to reflect region A about the line x = 3 and then again about the line y = 5, region A would lie right on top of region B. Thus, each lattice point in region A would correspond to exactly one lattice point in region B. Therefore, since f is one-one and onto it must be that P(A) = P(B). So the sum of their lattice points will always equal an even number. Thus, they will have no effect on the exponent -1 in the statement of the theorem. So we can omit them from the exponent leaving [pic].

Next we will show that the region [pic] contains [pic] lattice points where [pic] by showing that [pic] is the exact same number that occurred in Gauss’s Lemma when p = 11 and q = 19. Similarly, we will show that [pic] contains [pic] lattice points where [pic] by showing that [pic] is the exact same number that occurred in Gauss’s Lemma when p = 19 and q = 11. So we would have

[pic]

where [pic] must be congruent to [pic]mod 2.

Let [pic], by definition [pic] Since the length of the interval is only ½ it can only contain at most one integer y. There will be an integer y in this interval if and only if there is an integer [pic] in the interval

[pic].

which is if and only if

[pic]

or multiplying through by 11 we get the equivalent statement

[pic]

The integer in the middle, [pic], is the remainder on diving 19x by 11. Computing these remainders for the integers x in the range [pic], yields

for x = 1, [pic]

for x = 2, [pic]

for x = 3, [pic]

for x = 4, [pic]

for x = 5, [pic]

Thus, there are only three integers that lie within the range [pic] and 11, so [pic] = 3. If we recall from example 3, that the least residues for 19 with respect to 11 were -1, 2, -3, -4, and 5, so in this case s = 3 (remember that s is the number of negative least residues). We have [pic]= s = 3. Thus, the number of lattice points in[pic] is the exact same number which occurred in Gauss’s Lemma for [pic] By counting the number of lattice points in region [pic] on the graph we see there are indeed 3. So

[pic]

By using a similar argument we will show that the number of lattice points in [pic] is the same as the number of minus signs we found earlier using Gauss’s Lemma for

p = 19 and q = 11. Let [pic] by definition [pic] if and only if [pic] The interval again is only of length ½, so it will contain at most one integer x. There will be an integer x in this interval if and only if there is an integer [pic] in the interval

[pic]

which is true if and only if

[pic]

Multiplying through by 19 we obtain the equivalent statement

[pic]

The integer in the middle here is the remainder on dividing 11y by 19. Computing these remainders for the integers y in the range [pic] we see

for y = 1, [pic]

for y = 2, [pic]

for y = 3, [pic]

for y = 4, [pic]

for y = 5, [pic]

for y = 6, [pic]

for y = 7, [pic]

for y = 8, [pic]

for y = 9, [pic]

As we see there are only four integers that lie within the range [pic] to 19, so [pic] Again if we recall from example 4 that the least residues for 19 with respect to 11 were 1, -2, 3, 4, -5, 6, -7, -8, and 9 so in this case s = 4. So we have [pic] Thus, the number of lattice points in region [pic]corresponds exactly to the number which occurred in Gauss’s Lemma for [pic] Counting the number of lattice points on the graph we see that region [pic] does contain four lattice points. So [pic] Therefore, we have

[pic]

which is exactly what we wanted to show. ▲

5. Schmidt’s Proof

We are now ready to begin our examination of Hermann Schmidt’s proof. As stated in the introduction of this paper Schmidt’s proof uses some of the more elementary results in Number Theory such as the Chinese Remainder Theorem and Wilson’s Theorem. So we begin our discussion with these and a few related results.

Lemma 5: If (p, q) = 1, then [pic] if and only if [pic]and [pic].

Proof: [pic]Let p and q be two integers such that (p, q) = 1 and suppose that there exists integers x and a such that [pic] By definition of congruence if [pic]then[pic]. But if [pic] then [pic] and [pic] and so [pic] and [pic]which is what we wanted to show.

[pic] Let p and q be two integers such that (p, q) = 1 and suppose that there exists integers x and a such that [pic]and[pic]. If [pic]then by definition of congruence [pic]which implies that there exists and integer r such that (x – a) = rp. Similarly, if [pic]then by definition of congruence [pic]which implies that there exists an integer s such that (x – a) = sq. Now if (x – a) = rp and (x – a) = sq then rp = sq and so p must divide sq. But if [pic]then [pic]since it was assumed that (p, q) = 1. Hence there must exist an integer t such that tp = s. Thus (x – a) = sq = t(pq) which implies that [pic] and so [pic] which is what we wanted to show. ▲

Recall the Chinese Remainder Theorem, which assures the existence of a solution to any system of linear congruences over moduli that are pairwise relatively prime. In this paper, we only require a special case involving a pair of congruences, as stated in the next theorem. We include a proof for the sake of completeness.

Theorem 7: (Chinese Remainder Theorem): Let p and q be positive integers, with (p, q) = 1. Then the system of congruences

[pic] [pic]

has a solution. Furthermore, any two solutions will be congruent modulo pq.

Proof: Let p and q be two positive integers such that (p, q) = 1. Since (p, q) = 1, by the Euclidean Algorithm there must exist integers r and s such that rp + sq = 1. It follows that the integers sq and rp satisfy

[pic] [pic]

and [pic] [pic]

and so x = asq + brp must be a solution to the system of congruences[pic]and [pic]. This can be seen by reducing modulo p and then modulo q as follows,

[pic] and [pic]

Thus, if (p, q) = 1 the system of congruences [pic]and [pic]will have a solution.

If x is a solution, then adding any multiple of pq to x will still be a solution since [pic]for any integer k. Conversely if [pic] and [pic]are two solutions of the given congruences, then they must be congruent modulo p and modulo q, that is if

[pic] [pic]

and [pic] [pic]

then [pic] and[pic]. Thus [pic] is divisible by both p and q and so it is divisible by pq since by assumption (p, q) = 1. Therefore [pic]which is what we wanted to show. ▲

Example 12: To solve the system

[pic] [pic]

we first use the Euclidean Algorithm to write (2)(3) + (-1)(5) = 1. Then

x = (2)(3)(4) + (-1)(5)(1) = 19 is a solution and the general solution is x = 19 + 15t. The smallest nonnegative solution is therefore 4, so we have[pic]. ▲

Lemma 6: Let p and q be positive integers, with (p, q) = 1. If a is a quadratic residue modulo p and a is a quadratic residue modulo q then a is a quadratic residue modulo pq.

Proof: Suppose that a is a quadratic residue modulo p and modulo q. If a is a quadratic residue modulo p then there exists an x such that [pic]. Considering the list of integers x, x + p, x + 2p, . . . . . , x + (q – 1)p we have that

[pic]

in some order. Since a is also a quadratic residue modulo q at least one of the numbers from this second list, call it y, when squared, must yield a modulo q. That is, [pic] But y must be congruent to one of the numbers in the list

x, x + p, x + 2p, . . . . . , x + (q – 1)p. In other words, [pic] for some integer i. Now we have that [pic] and also [pic] If [pic]then [pic] Thus we have that [pic] and [pic]so[pic] by Lemma 5. Hence a is quadratic residue modulo pq. ▲

Next we would like to recall Wilson’s Theorem which allows us to determine for what integers p, p is a prime.

Theorem 8: (Wilson’s Theorem): Let p be an integer. Then p is a prime if and only if [pic]

Proof: If p = 2, then [pic]as desired. So assume that p is an odd prime. For the rest of the proof we will assume that p is an odd prime.

[pic]If p is an odd prime and G = {1, 2, . . . . , p – 1} then by Lemma 2 each a in G will have a unique inverse modulo p. If[pic], then multiplying both sides of this congruence by a yields [pic]. If [pic]then [pic] or equivalently[pic]. Given that p is prime, [pic]implies [pic]and so a = 1 or a = p – 1. Thus, 1 and p – 1 are each their own inverses, but every other element of G has a distinct inverse, and so if we collect the elements of G pairwise and multiply them all together we have

[pic]

but

[pic]

Hence

[pic].

[pic] Now suppose by contradiction that the congruence holds for a composite number p. If p is composite then p has a proper divisor d with 1 < d < p. If d < p then d also divides [pic] since d must be one of the integers between 1 and p – 1. However, we assumed the congruence [pic]holds so d must also divide (p – 1)! + 1 and so d must divide 1 which a contradiction. Thus if the congruence holds p must be prime which is what we wanted to show. ▲

Example 13: Let p = 11, then we should be able to pair the integers from 1 to 10[pic], not inclusive, with their inverses. Indeed,

[pic], [pic], [pic], [pic]

Thus,

[pic] ▲

With Wilson’s Theorem and the Chinese Remainder Theorem established we will begin our exploration of Schmidt’s proof, which may be found in his paper entitled Drei neue Beweise des Reciprocitätssates in der Theorie der quadratischen Reste, beginning with the following lemma.

Lemma 7: Let p, q be distinct odd primes. If r denotes any quadratic residue (mod pq), then the congruence [pic]has exactly four distinct solutions, [pic] through [pic] that satisfy: (1) [pic]

(2) [pic]

In particular, two solutions have positive least residues modulo pq.

Proof: Assume r is a quadratic residue mod pq. Then the congruence [pic]has solutions mod pq. So by Lemma 5, this congruence has solutions mod p and mod q. Indeed, by Proposition 1, [pic]has exactly two incongruent solutions mod p, call them c and –c. Similarly, [pic] has exactly two incongruent solutions mod q, call them d and – d.

Therefore [pic]must have exactly four solutions [pic], [pic], [pic], and [pic], each satisfying a pair of congruences as follows:

(i) [pic] and [pic]

(ii) [pic] and [pic]

(iii) [pic] and [pic]

(iv) [pic] and [pic]

By the Chinese Remainder Theorem [pic] through [pic] are each uniquely determined (mod pq). Moreover, [pic] through [pic] are all distinct (mod pq) by construction. Observe that [pic]and [pic] modulo pq and so the conditions of the Lemma are satisfied. ▲

Definition 6: If r is any quadratic residue modulo pq then we say the four solutions of [pic] are conjugates.

Corollary 3: When the p and q are distinct odd primes then the number of quadratic residues modulo pq is exactly[pic].

Proof: By the above lemma, each of the (p – 1)(q – 1) residues prime to pq belongs to a set of four conjugates whose squares are congruent modulo pq to a common quadratic residue. It follows that there are exactly [pic] quadratic residues modulo pq. ▲

Remark

By the Lemma 7, it follows that for odd primes[pic], there will be four solutions to [pic]. If we consider the least residues of these solutions, two will be positive and two will be negative. Clearly[pic] is one of the positive solutions. We henceforth will use [pic] to denote the remaining positive solution.

Lemma 8: Let p, q denote distinct odd primes. Let [pic] through [pic] represent the four conjugates stated in Lemma 7 satisfying:

(1) [pic]

(2) [pic]

Let a and b be two remainders such that [pic] and [pic]. Let r be any quadratic residue modulo pq.

i) If[pic], then exactly one of the four solutions of [pic] is itself a quadratic residue, the other three are not.

ii) If [pic] and [pic](or visa versa) then either exactly two of the four solutions of [pic] are quadratic residues or else none of them are.

iii) If [pic]then either all four solutions of [pic]are quadratic residues, or else none of them are.

Proof (i): Let p and q be odd primes such that[pic]. Then by Corollary 1, either a or –a is a quadratic residue modulo p. Similarly either b or –b is a quadratic residue modulo q. Thus we have the following four cases:

Case 1: (a and b are both quadratic residues)

Assume that a and b are quadratic residues modulo p and q respectively.

If a is a quadratic residue modulo p then by definition of a and (1) above, [pic] and [pic]are both quadratic residues modulo p. Similarly if b is a quadratic residue modulo q then by definition of b and (2) above, [pic] and [pic] are quadratic residues modulo q. Hence [pic] is a quadratic residue modulo pq by Lemma 6 and the others are not.

Case 2: (- a and b are quadratic residues)

Assume that –a and b are quadratic residues modulo p and q respectively. If –a is a quadratic residue modulo p then [pic] and [pic] are both quadratic residues modulo p by definition (1) above. If b is a quadratic residue modulo q then[pic]and [pic] are both quadratic residues modulo q by definition (2) above. Hence[pic] is a quadratic residue modulo pq by Lemma 6 and the others are not.

Case 3: (a and –b are quadratic residues)

Assume that a and –b are quadratic residues modulo p and q respectively. If a is a quadratic residue modulo p then [pic] and [pic] are both quadratic residues modulo p by definition (1) above. If –b is a quadratic residue modulo q then[pic]and [pic] are both quadratic residues modulo q by definition (2) above. Hence[pic] is a quadratic residue modulo pq by Lemma 6 and the others are not.

Case 4: (– a and –b are quadratic residues)

Assume that –a and –b are quadratic residues modulo p and q respectively. If –a is a quadratic residue modulo p then [pic] and [pic] are both quadratic residues modulo p by definition (1) above. If –b is a quadratic residue modulo q then[pic]and [pic] are both quadratic residues modulo q by definition (2) above. Hence[pic] is a quadratic residue modulo pq by Lemma 6 and the others are not.

Thus we have shown that when [pic] in each of these cases only one of the solutions [pic]through [pic] is a quadratic residue modulo pq, which is what we wanted to show.

Proof (ii): Without loss of generality, assume[pic]and [pic]. If [pic]then a and –a are either both quadratic residues or quadratic nonresidues modulo p. Thus we have the following two cases:

Case 1: (a, –a and b or –b are quadratic residues)

Assume that a and –a are both quadratic residues modulo p then by definition (1) we have that[pic], [pic], [pic], and [pic]are all quadratic residues modulo p. Now since[pic], if b is a quadratic residue modulo then by Corollary 1, – b is a quadratic nonresidue and visa versa. If b is a quadratic residue modulo q then by definition (2) above [pic] and [pic] are quadratic residues modulo q. Thus by Lemma 6, [pic]and [pic] would be quadratic residues modulo pq and [pic]and [pic]would not. Similarly if – b is a quadratic residue modulo q then by definition (2) above [pic] and [pic]are quadratic residues modulo pq. Thus by Lemma 6, [pic]and [pic]would be quadratic residues modulo pq and [pic]and [pic]would not. In either case exactly two of the solutions [pic] through[pic] are quadratic residues modulo pq.

Case 2: (a and –a are quadratic nonresidues)

Assume that a and –a are quadratic nonresidues modulo p then [pic] through[pic] are quadratic nonresidues modulo p. Therefore[pic] through[pic] are quadratic nonresidues modulo pq.

Thus we have shown that if [pic] and [pic](or visa versa) then exactly two of the conjugates are quadratic residues modulo pq or none of them are. Which is what we wanted to show.

Proof (iii): Let[pic]. If [pic]then both a and – a are either both quadratic residues or both quadratic nonresidues modulo p. Similarly, if [pic]both b and – b are either both quadratic residues or both quadratic nonresidues modulo q. Thus we have the following two cases:

Case 1: (a, – a , b, – b are all quadratic residues) Assume that a, –a are quadratic residues modulo p and b, – b are quadratic residues modulo q. Then all four solutions are quadratic residues modulo p and modulo q. Hence by Lemma 6, all four solutions would be quadratic residues modulo pq.

Case 2: (a, – a quadratic nonresidues or b, – b quadratic nonresidues)

Without loss of generality assume that a and –a are quadratic nonresidues modulo p. Then all of the four solutions [pic] through[pic]are quadratic nonresidues modulo p. Hence all four solutions are quadratic residues modulo pq.

We have shown that if [pic]then all four of the solutions are quadratic residues modulo pq or none of them are, which is what we wanted to show. ▲

Example 14: This example illustrates the case when both p and q are congruent to 3 modulo 4. Let p = 3 and q = 7 then the (p – 1)(q – 1) =(2)(6) = 12 remainders prime to 21 are 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20. Squaring each of these numbers and reducing them modulo 21 we have

[pic]{– 1, 1, – 8, 8} solve [pic]

[pic]{– 2, 2, – 5, 5} solve [pic]

[pic]{– 4, 4, – 10, 10} solve [pic]

So we can easily see that there are exactly four remainders, two negative and two positive, whose squares are congruent modulo 21. Observe that each set of four contains exactly one quadratic residue. If we choose the remainders – 5 and 5 then –a = - 2 , a = 2, –b = - 5 and b =5. Thus our four conjugates will be

[pic] and [pic]

[pic] and [pic]

[pic] and [pic]

[pic] and [pic]

Since p = 3 is congruent to 3 mod 4 and so only one of the numbers

– 2 or 2 is a quadratic residue modulo 3. If we square the numbers 1 and 2 we see

[pic] and [pic]

and so – 2 is a quadratic residue modulo 3 and 2 is not. Similarly q = 7 is congruent to 3 mod 4 and so only one of the numbers – 5 or 5 is a quadratic residue modulo 7. If we square the numbers from 1 to 6 and reduce each modulo 7 we have

[pic] [pic] [pic]

[pic] [pic] [pic]

and so – 5 is a quadratic residue modulo 7 and 5 is not. Thus the conjugate [pic] is the only quadratic residue modulo 21. If [pic] and [pic]then [pic] and – 5 is a quadratic residue modulo 21 since [pic]and [pic] ▲

Example 15: This example illustrates the case when either p or q is congruent to 1 modulo 4. Let p = 3 and q = 5 then the (p – 1)(q – 1) =(2)(4) = 8 remainders prime to 15 are 1, 2, 4, 7, 8, 11, 13, 14. Squaring each of these numbers and reducing them modulo 15 we have

[pic]{– 1, 1, – 4, 4} solve [pic]

[pic]{– 2, 2, – 7, 7} solve [pic]

So we can easily see that there are exactly four remainders, two negative and two positive, whose squares are the same or congruent modulo 15. Observe that the first set of four contains exactly two quadratic residues and the other does not contain any. If we choose the remainders – 4 and 4 then –a = - 1, a = 1, –b = - 4 and b =4. Thus our four conjugates will be

[pic] and [pic]

[pic] and [pic]

[pic] and [pic]

[pic] and [pic]

Since p = 3 is congruent to 3 mod 4 only one of the numbers – 1 or 1 is a quadratic residue modulo 3. If we square the numbers 1 and 2 we see

[pic] and [pic]

and so 1 is a quadratic residue modulo 3 and -1 is not. Now q = 5 is congruent to 1 mod 4 and so either the numbers – 4 and 4 are both quadratic residues or both quadratic nonresidues modulo 5. If we square the numbers from 1 to 4 and reduce each modulo 5 we have

[pic] [pic] [pic] [pic]

and so – 4 and 4 are both quadratic residues modulo 5. Thus the conjugates [pic]and [pic]must be quadratic residues modulo 15. If [pic] and [pic]then [pic] and 4 is a quadratic residue modulo 15 since[pic] If [pic] and [pic]then we can determine the quadratic residue modulo 15 by using the method implied by the proof of the Chinese Remainder Theorem. By the Euclidean algorithm (3)(2) + (5)(-1) =1 and so a solution to the system is

x = (3)(2)(-4) + (5)(-1)(1) = -29 and so the smallest nonnegative solution[pic]. Thus 1 is a quadratic residue modulo 15 since [pic] ▲

Example 16: This example illustrates the case when both p and q are congruent to 1 modulo 4. Let p = 5 and q = 13 then squaring the (p – 1)(q – 1) =(4)(12) = 48 remainders prime to 65 and reducing each of modulo 65 we have

{– 1, 1, – 14, 14} solve [pic] {– 8, 8, – 18, 18} solve [pic]

{– 2, 2, – 28, 28} solve [pic] {– 11, 11, – 24, 24} solve [pic]

{– 3, 3, – 23, 23} solve [pic] {– 12, 12, – 27, 27} solve [pic]

{– 4, 4, – 9, 9} solve [pic] {– 16, 16, – 29, 29} solve [pic]

{– 6, 6, – 19, 19} solve [pic] {– 21, 21, – 31, 31} solve [pic]

{– 7, 7, – 32, 32} solve [pic] {– 17, 17, – 22, 22} solve [pic]

So we can easily see that there are exactly four remainders, two negative and two positive, whose squares are the same or congruent modulo 65. Observe also that each set of four contains either exactly four or zero quadratic residues. If we choose the remainders – 14 and 14 then –a = - 4 , a = 4, –b = - 1 and b =1. Thus our four conjugates will be [pic] and [pic]

[pic] and [pic]

[pic] and [pic]

[pic] and [pic]

Since p = 5 is congruent to 1 mod 4 either both of the numbers –4 and 4 are quadratic residues modulo 5 or both quadratic nonresidues modulo 5. If we square the numbers from 1 to 4 we see

[pic] [pic] [pic] [pic]

and so – 4 and 4 are both quadratic residues modulo 5. Similarly q = 13 is congruent to 1 mod 4 and so either both of the numbers – 1 and 1 are quadratic residues modulo 13 or both are quadratic nonresidues modulo 13. If we square the numbers from 1 to 6 and reduce each modulo 7 we have

[pic] [pic] [pic] [pic] [pic] [pic]

and so –1 and 1 are both quadratic residues modulo 13. Thus all four conjugates must be quadratic residues modulo 65. If [pic] and [pic]then by the Euclidean Algorithm 1 = (2)(13) + (-5)(5) and so a solution to the system is

x = (2)(13)(4) + (-5)(5)(1) = 79 which implies that the smallest nonnegative solution is

[pic]. Thus 14 is a quadratic residue modulo 65. If [pic] and [pic]then by the C.R.T a solution to this system is x = (2)(13)(4) + (-5)(5)(-1) = 129 which implies that the smallest nonnegative solution is [pic]. Thus 64 is a quadratic residue modulo 65. If [pic] and [pic]then by the C.R.T. a solution to this system is x = (2)(13)(-4) + (-5)(5)(1) = -129 which implies that the smallest nonnegative solution is [pic] and 1 is a quadratic residue modulo 65. Finally, if [pic] and [pic] then by the C.R.T. a solution to this system is x = (2)(13)(-4) + (-5)(5)(-1) = -79 which implies that the smallest negative solution is [pic] and 51 is also a quadratic residue modulo 65. ▲

Throughout the discussion of the next few lemmas and corollary we will be examining and referring to a particular product which we will define here.

Definition 7: We will define[pic] to be the product of positive remainders that are prime to pq. That is, [pic]

Lemma 9: Let p and q be distinct odd primes.

i) If[pic] then[pic][pic].

ii) Otherwise,

[pic] and [pic][pic].

Proof (i): If we assume that both p and [pic]then both +1 and -1 are quadratic residues modulo p and modulo q. So by Lemma 6, – 1 is a quadratic residue modulo pq. Thus by Lemma 7 we have four remainders modulo pq whose squares are congruent – 1 (mod pq), of these, two are positive, we will denote one by[pic], and the other by [pic], where [pic] Thus we have four remainders 1, [pic][pic] and [pic]whose squares and product are [pic] For each of the remaining positive remainders a of pq there exists a unique remainder b such that [pic] and so the entire product [pic]

Proof (ii): In the case where (p – 1)/2 or (q – 1)/2 is odd, that is when either p or q is congruent to 3 modulo 4, then -1 is a quadratic nonresidue modulo pq. Grouping all of the remaining positive remainders we have [pic], [pic], etc. when reduced modulo pq. Thus, in all of the remaining cases we have that [pic] ▲

Corollary 4: Let p and q be distinct odd primes. Then

[pic]

Proof: The exponent [pic] is even if and only if p and [pic]. So this corollary holds by the work above. ▲

Lemma 10: Let p and q be distinct odd primes. Then

[pic]

Proof: In order to determine the signs on [pic] and [pic] we will proceed by looking at the following product:

[pic] (1)

If we consider this product modulo p then we obtain

[pic]

Now by Wilson’s Theorem we have that [pic]and so

[pic]

Hence

[pic]

Comparing this product to [pic] we note that both products contain the same number of factors, namely (p – 1) [pic]. We can derive the product in (1) from the product [pic] by multiplying by [pic] and dividing by

[pic].

That is,

[pic] [pic]

But

[pic]

Thus

[pic]

or equivalently

[pic]

or

[pic]

or multiplying both sides by [pic] we have

(I) [pic].

If we were to do the same analysis interchanging the roles of p and q we would obtain

the congruence

(II) [pic].

If we multiply (I) and (II) we obtain

[pic]

Which is what we wanted to show. ▲

The result of the Law of Quadratic Reciprocity thus follows directly, as follows.

Proof of the Law of Quadratic Reciprocity: By Corollary 3 we have that [pic] and by the previous Lemma 8 we have just shown that [pic] Thus we have that

[pic][pic].

Dividing both sides of this equality by [pic] and subtracting exponents, the reader could easily verify that this expression simplifies to

[pic].

Which is what we wanted to show. ▲

Example 17: This next example illustrates Lemma 7 for the case where p = 5 and q =13.

Let p = 5 and q = 13. Then

[pic]

[pic]

Given that 5 and 13 are both congruent to 1 modulo 4 we know that both -1 and 1 are quadratic residues modulo 65. We can see this is true by the congruences below

[pic] and [pic]

[pic] and [pic]

Thus we have the four positive remainders 1, [pic][pic][pic]= 1, 14, 8, [pic] whose product [pic] Now we will pair each of the following positive remainders with their unique inverses as follows:

[pic] [pic] [pic]

[pic] [pic] [pic]

[pic] [pic] [pic]

[pic].

Thus considering the product [pic] modulo 65 yields

[pic]

[pic]

[pic] (since [pic])

[pic]. ▲

Example 18: This next example illustrates Lemma 7 for the case when either p or q is congruent to 3 modulo 4. Let p = 5 and q = 11. Then

[pic]

[pic]

Given that 11 is congruent to 3 modulo 4 we know that 1 is a quadratic residue modulo 55 and -1 is not. We can easily see from the following congruences that 1 is a quadratic residue modulo 55

[pic] and [pic].

Thus we have the two positive remainders 1 and [pic]= 1 and 21 whose squares are [pic] Now we will pair each of the following positive remainders with their unique inverses as follows:

[pic] [pic] [pic]

[pic] [pic] [pic]

[pic] [pic] [pic]

Thus considering the product [pic] modulo 55 yields

[pic]

[pic]

[pic]

[pic].

Now [pic] and [pic]. Thus [pic] and so exactly one of the congruences [pic]and [pic]and the other is not. It might be easiest to check the congruence[pic]since it reduces to [pic]. By Lemma 3, the congruence [pic] is solvable since [pic]. Therefore, by the Law of Quadratic Reciprocity, the congruence [pic] is not solvable. ▲

6. Conclusion

The Law of Quadratic Reciprocity has been an important theme in the development of number theory. Since the time of Gauss, many other mathematicians such as Cauchy, Jacobi, and Kronecker have all devised their own proofs of the law to determine for themselves why such a deep reciprocal relationship should exist between simple congruences linking any pair of odd primes.

To date there are over 200 published proofs for the Law of Quadratic Reciprocity. As was mentioned earlier Gauss provided several proofs himself, eight to be exact, which were all motivated by his desire to generalize the law to higher powers. The search for higher reciprocity laws eventually led to the development of a new field of mathematics known as algebraic number theory.

References

Beachy, John A., and William D. Blair. Abstract Algebra. Prospect Heights: Waveland

Press Inc., 1996.

Bell, E. T., Men of Mathematics. New York: Simon and Schuster, 1937.

Buhler, W.K., Gauss: A Biographical Study. New York: Springer-Verlag, 1981.

Burn, R. P., A Pathway into Number Theory. New York: Cambridge University Press,

1997.

Burton, David M., Elementary Number Theory. Iowa: Wm. C. Brown Publishers, 1989.

Cohn, Harvey, A second Course in Number Theory. New York: John Wiley & Sons,

Inc., 1962.

Dunham, William, Journey Through Genius. New York: Penguin Books, 1991.

Goldman, Jay R., The Queen of Mathematics: A Historically Motivated Guide to

Number Theory. Wellesly: A K Peters, 1998.

Hall, Tord, Carl Friedrich Gauss. Trans. Albert Froderberg. Cambridge: MIT, 1970.

Long, Calvin T., Elementary Introduction to Number Theory. New York: D.C. Heath

and Company, 1965.

Reich, Karin, Carl Friedrich Gauss. Trans. Patricia Crampton. Munich: Heinz Moos

Verlag, 1977.

Rousseau, G. On the Quadratic Reciprocity Law. Journal of Australian Mathematical

Society (Series A). 51 (1991) 423-425.

Schmidt, H. Drei neue Beweise des Reciprocitatssatzes in der Theorie der quadratischen

Reste., Journal Reine Angew. Math. 111 (1893), 107-120.

Schumer, Peter D., Introduction to Number Theory. Boston: PWS Publishing Company,

1996.

Smith, David Eugene, A Source Book in Mathematics. New York: McGraw-Hill Book

Company, Inc., 1929.

“The Law of Quadratic Reciprocity.”

. Math.nott.ac.uk/personal/jec/courses/G13NUM/notes/node20.html.

“The Jewel of Arithmetic: Quadratic Reciprocity.”

.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download