Related Links (Outside this Site)

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

Let  p  be an  odd prime  dividing  n²+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 necessarily a  field ).  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 has two sets of 2 elements besides sets with 4 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,  in a unique way).  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.

Why was this visual proof missed for 400 years? (33:58)  by  Burkar Polster  (Mathologer, 2020-01-25).

Number	Possible Prime Factors
n2 + 1	2,   4k+1
n2 - 2	2,   8k+1,   8k+7
n2 + 2	2,   8k+1,   8k+3
n2 - 3	2,   3,   12k+1,   12k+11
n2 + 3	2,   3,   12k+1,   12k+7
n2 - 5	2,   5,   10k+1,   10k+9
n2 + 5	2,   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

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

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. 

More than 200 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.

A  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:

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

Those are all distinct because the residue ring  / p  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.

(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). 

(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 ) p

=

0    if  p  divides  a , 1 if  a  is a quadratic residue modulo  p , -1 otherwise.

For typographical reasons, we'll 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 symmetrical relationship between  (m|n)  and  (n|m)  when  m  and  n  are  both  odd primes.  This relation  (the 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 would be nice to consistently define the meaning of the symbol for less restricted arguments, while maintaining the above.

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  base,  of 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 defined 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.

(2 | q)   =   (-1)^(q2-1)/8

(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.

The late  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 liked 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 there's only one residue class  "modulo -1"  and it's therefore equal to its own square!

Theorem of the Day #29  by  Robin Whitty
 
Quadratic Reciprocity (56:36)  by  Burkar Polster  (Mathologer, 2020-03-14).

(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  < a >  the  integer congruent to  a  which is between  -p/2  and  +p/2.  Gauss' lemma  states that

( a ) p

=

(p-1)/2 Õ 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:

F

( a ) p

=     F  a (p-1)/2     =

(p-1)/2 Õ j = 1

< j a >

=     F

(p-1)/2 Õ 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}. 

(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 r  has an  even  least positive remainder modulo p 

(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.

(2017-11-21)   Cubic reciprocity  &  Eisenstein integers

Cubic reciprocity   |   Eisenstein integers   |   Unique factorization domain (UFD)
"...entiers complexes cubiques" (1908)  Raymond Le Vavasseur  (1862-1930; ENS 1888">ENS 1883).

(2017-11-21)   Quartic reciprocity  &  Gaussian integers

Quartic reciprocity   |   Gaussian integers   |   Carl F. Gauss (1777-1855)

(2017-11-21)   Eisenstein Reciprocity   (1850)
Extending laws of reciprocity to higher powers.

Eisenstein reciprocity   |   Gotthold Eisenstein (1823-1852)

(2006-06-11)   Artin's Reciprocity   (1927)
A generalization due to Emil Artin (1898-1962).

This is a partial solution to  Hilbert's ninth problem.

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

(2019-04-06)   Adele Rings
The structures which  Artin reciprocity  begat.

Adele ring   |   Algebraic number theory   |   Class field theory