home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2017   Gérard P. Michon, Ph.D.

Reciprocity Laws

 Leonhard Euler 
 (1707-1783)  Adrien-Marie Legendre 
 (1752-1833) knighted in 1811  Carl Friedrich Gauss 
God does arithmetic.
Carl Friedrich Gauss (1777-1855) 

Related articles on this site:

Related Links (Outside this Site)

Schauspiel  about the third proof by Gauss of the  law of quadratic reciprocity.
More than 200  proofs of the quadratic reciprocity law.
Zolotarev's Lemma.
Reciprocity Laws:  from Euler to Eisenstein  by  Franz Lemmermeyer 

On the Law of Quadratic Reciprocity
The  Aureum Theorema  (golden theorem)  of  Carl F. Gauss.

(2006-06-03)   Early Examples and Motivation   (Girard, 1632)
About the prime divisors of some  quadratic forms...

Let  p  be an  odd prime  dividing  n2+1  where  n  is an integer.  Modulo p, the residue class of  n  is a "square root of -1"  which we'll call  "i"  (as their squares are opposites, i and 1 are distinct, since p ¹ 2).

Modulo a prime number, the residues form a field  (a  finite  ring without divisors of zero is necessarilyfield ).  The  p-1  nonzero residues, may be partitioned into disjoint sets, each containing the opposites and the reciprocals of its own elements.  The  finest  (i.e., "least coarse")  such partition contains two sets of 2 elements and a number of sets with 4 distinct elements,  viz.

{1,-1}     {i,-i}     {x,-x,1/x,-1/x}     (for any  x  besides  1, -1, i ,-i )

Thus,  p-1  must be a multiple of 4  (conversely, modulo any such prime  p,  there must be a residue  i  with a square congruent to -1  or else the lack of the second pair above would mess up the count).  This result was first stated in 1632, without proof, by  Albert Girard (1595-1632).  It's the first line in the following table.

In fact, Girard conjectured that a lot more was true,  namely that any prime  p  of the form  4n+1  could always be written as the sum of two perfect squares.  Fermat offered a proof of that in a letter to Mersenne dated 1640-12-25  (Christmas day).  So, the result became known as  Fermat's Christmas Theorem.

 Number Possible Prime Factors
n2 + 12,   4k+1
n2 - 22,   8k+1,   8k+7
n2 + 22,   8k+1,   8k+3
n2 - 32,   3,   12k+1,   12k+11
n2 + 32,   3,   12k+1,   12k+7
n2 - 52,   5,   10k+1,   10k+9
n2 + 52,   5,   20k+1,   20k+3,   20k+7,   20k+9
n2 - 6  2,   3,   24k+1,   24k+5,   24k+19,   24k+23  
n2 + 6  2,   3,   24k+1,   24k+5,   24k+7,   24k+11  

 Leonhard Euler 

Euler conjectured that, for any prime  q,  any prime factor  p  of  n2-q  (besides, possibly, p=2 and p=q)  must be of the form   4qk+b2   or   4qk-b2   for some odd integer  b.  That's the earliest statement of the  law of quadratic reciprocity.

 Adrien-Marie Legendre 

Although special cases had been noted by Euler and Lagrange, the fully general theorem is credited to Legendre, who devised a special notation to express it. 

 Carl Friedrich Gauss 

More than a hundred proofs of this  deep  result have been tallied.  Carl Friedrich Gauß found the first of these in 1795 and published it in  Section 4  of Disquisitiones Arithmeticae  (1796).  He came up with no fewer than  8  different proofs over his lifetime.  None of these truly satisfied him, though...  Apparently, the multitude of proofs serves only to increase the mystery shrouding the  law of quadratic reciprocity,  which Gauß dubbed  Aureum Theorema  (the golden theorem).  The following articles present this  golden  topic, which once stirred the enthusiasm of the great Gauss.

(2006-05-31)   Quadratic Residues
Modulo an odd prime,  half  the nonzero residues are squares.

quadratic residue  is simply the congruence class of a square.  The term is usually reserved to  nonzero  residues.  By contrast, a residue which is not congruent to any square is sometimes called a  quadratic nonresidue  [sic].

Modulo an odd prime  p,  there are just  (p-1)/2  quadratic residues, namely:

12,   22,   ...   [(p-1)/2]2     (modulo p)

Those are all distinct because the residue ring  Z / pZ  is known to be a field  (a  finite  ring can be proven to be a  field  if there are no divisors of zero in it).  In a field,  x  and  y  have the same square if and only if

(x-y) (x+y)   =   0

This implies that  y  is either  x  or  -x  (these two are distinct, since the field at hand is  not  of characteristic 2).  The opposite of a residue  x  being of the form  p-x,  the above does enumerate all the  quadratic residues  modulo p.

 Leonhard Euler 
 (1707-1783) (2006-05-31)   Euler's Criterion   (modulo an odd prime  p )
How to tell whether a given residue is congruent to a square.

Leonhard Euler (1707-1783) devised the first effective test to tell  quickly  whether a  given  residue is a quadratic residue or not.  This is known as  Euler's criterion :  Modulo an  odd prime  p,  the nonzero residue  a  is a quadratic residue  if and only if  the following equation is true, modulo p :

a (p-1)/2   =   1

This is easily established by considering a  primitive root  g  (i.e., a residue generating multiplicatively the group of the  p-1  nonzero residues modulo p).  The even powers of  g  are quadratic residues and the odd powers are not.

In particular,  g  itself can't be a quadratic residue  (the order of  g  must be  p-1,  and it would be at most  (p-1)/2  if  g  was congruent to the square of some  x,  since the order of  x  divides  p-1,  by Fermat's little theorem).

If  a  is an even power of  g , the above relation holds  (as the left-hand side is something raised to the power of p-1).  Conversely, if  a  is an odd power of  g,  then the left-hand side is congruent to  g  raised to  (p-1)/2  which must be congruent to -1  (as it can't be congruent to 1 while its square is).  QED

 Adrien-Marie Legendre 
 (1752-1833)  knighted in 1811 (2006-05-31)   The Legendre Symbol and its Generalization(s)
The original definition was generalized by Jacobi and Kronecker.

Part of the secret of analysis is the art of using notations well.
Gottfried Wilhelm von Leibniz   (1646-1716) 

Original definition, by  Adrien-Marie Legendre  (1752-1833)

At first, the  Legendre symbol  (a|p)  was defined as follows,
for any integer  a  and  [only]  for an  odd prime  p.

( a )
=  Alternatives
0   if  p  divides  a ,
1if  a  is a quadratic residue modulo  p ,

For obvious typographical reasons, we use the "horizontal" version  (a|p)  of the symbol, although the more traditional "vertical" version is preferred in print.

Euler's criterion, as discussed above, may thus be simply expressed:

If  p  is an odd prime,  then     (a|p)   =   a (p-1)/2   (modulo p).

The Legendre symbol was introduced specifically to stress the nice symmetrical relationship between  (m|n)  and  (n|m)  when  m  and  n  are  both  odd primes.  This relation  (the very law of quadratic reciprocity)  is expressed by the last two of the following fundamental properties of the  Legendre symbol :

  • (m|n)  Π { -1, 0, +1 }
  • If  a  is congruent to  b  modulo  n,  then   (a|n)  =  (b|n)
  • ( ab | n )   =   (a|n) (b|n)
  • (n|m)  =  (m|n)   unless  n  and  m  are  both  congruent to 3 modulo 4.
  • (n|m)  =  -(m|n)   if  n  and  m  are  both  congruent to 3 modulo 4.

[ Skip  the rest of this article on first reading. ]

It was later realized that it could be useful to consistently define the meaning of the symbol for less restricted arguments, while maintaining the above properties.

Although it's traditionally done, there's no compelling reason to call a generalized version of the  Legendre symbol  by any other name...  The  Jacobi symbol  and  Kronecker symbol  are just to the restricted  Legendre symbol  what real and complex exponents are to integral exponents  [ for a  positive  baseof course ].

Generalization, by  Karl Gustav Jacobi  (1804-1851)

Jacobi has defined  (a|k)  for any  odd  integer  k  by adding the simple rule:

  • (a|mn)  =  (a|m) (a|n)

Further generalization, by  Leopold Kronecker (1823-1891)

Kronecker proposed to define the symbol for  all  integers by adding the rules:

  • (n | -1)  =  sign(n)
  • (2n | 2)  =  0
  • (8n+1 | 2)  =  (8n-1 | 2)  =  1
  • (8n+3 | 2)  =  (8n-3 | 2)  =  -1

Some authors argue that the above  needlessly  defines the symbol  (n|2)  when  n  is congruent to 2, 3, 6 or 7 modulo 8.  They'd rather leave such cases  undefined.

(2006-05-31)   The  Basic  Law of Quadratic Reciprocity
Shuning later generalizations, this law states a simple but surprising fact:

For two distinct  odd primes  p  and  q,  the following statements are either both true or both false,  unless  p and q are  both  congruent to 3 modulo 4, in which case one statement is true and the other is not:

  • p  is a  quadratic residue  modulo q.
  • q  is a  quadratic residue  modulo p.

John Conway  has observed  (video)  that the exact same statement also holds if either  p  or  q  is equal to  -1.  For this and other reasons, Conway likes to consider  -1  to be an odd prime which has only two powers  (+1 and -1)  instead of infinitely many.  (This viewpoint allows a natural extension of the  fundamental theorem of arithmetic  to negative integers.)

Indeed,  q = -1  is  clearly  a  quadratic residue  modulo an odd prime  p  when  p  isn't congruent to 3 modulo 4  (Girard, 1632).  Conversely,  when  p  is congruent to 3 modulo 4  (so that both p and q are)  then  -1  isn't a  quadratic residue  modulo p.  Thus, the law stated above holds if and only if the following statement is properly interpreted so that it holds true:

p  is a quadratic residue modulo  -1.

That's trivially the case because thare's only one residue class  "modulo -1"  and it's therefore equal to its own square!

Theorem of the Day

 Carl Friedrich Gauss 
 (177-1855) (2006-05-15)   Gauss' Lemma
The Legendre symbol  (a|p)  is the product of  (p-1)/2  signs.

For a given  odd prime  p,  let's denote  < athe  integer congruent to  a  which is between  -p/2  and  +p/2.  Gauss' lemma  states that

( a )
j = 1
   sign < j a >

Proof :   Since the result is trivial when  p  divides  a  (the sign of 0 being 0)  we may assume that  a  is invertible modulo p.

The  absolute values   | < j a > |   are all distinct, since  a  is invertible modulo p   [otherwise, distinct values of  j  would be either equal or opposite modulo p, which is ruled out in the range from  1  to  (p-1)/2].  These absolute values thus assume all the values from  1  to  (p-1)/2,  once and only once  (the  pigeonhole principle )  and their product  F  is the factorial of  (p-1)/2.  Therefore, (using Euler's criterion) we have the following equalities, modulo p:

( a )
    =     F  a (p-1)/2     =    
j = 1
  < j a >     =     F  
j = 1
   sign < j a >

The result follows by cancelling  F  (which is coprime to  p)  and observing that equality modulo p  certainly implies equality in the range  {-1,+1}.  QED

(2006-06-07)   Eisenstein's Lemma   (Gotthold Eisenstein, 1844)
Proposed in 1844 to simplify the  1808  third proof  of Gauss.

The idea and the result are similar to Gauss's lemma, except that the nonzero residues  (modulo an  odd prime  p)  are split into even and odd ones, instead of being split into low and high ones, as in Gauss' original lemma.

If  r  is the (least positive) remainder of  ja  modulo p,  then  (-1)r  has an  even  least positive remainder modulo p 

 Come back later, we're
 still working on this one...

(2006-06-08)   Proving the Law of Quadratic Reciprocity
A modern proof based on Gauss' Lemma.

To use Gauss' lemma when  a  is between  1  and  p-1,  we may use the following pseudocode to count the number of times  k  for which  x = < j a >  is negative:

x := 0   ;   k := 0   ;
for  j := 1  to  (p-1)/2
    x  :=  x + a
    if  x > p   then   x := x - p
    if  x > p/2   then   k := k+1
next j

Despite its simple appearance, this procedure is  much lesss  efficient than a fast implementation of Euler's criterion.  Nevertheless, it makes things easier to tally from a theoretical standpoint.

 Come back later, we're
 still working on this one...

Emil Artin,
March 3, 1898,
Dec. 20, 1962.
(2006-06-11)   Artin's Reciprocity   (1927)
A generalization due to Emil Artin (1898-1962).

 Come back later, we're
 still working on this one...

Artin's Reciprocity and Mersenne Primes (pdf) by H.W. Lenstra Jr. and P. Stevenhagen  (March 2000).

visits since May 31, 2006
 (c) Copyright 2000-2017, Gerard P. Michon, Ph.D.