Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Gauss' Lemma

Gauss' Lemma on quadratic residues

If p is an odd prime, and a is an integer coprime to p, then let n be the number of elements of {a, 2a, 3a, ..., ((p-1)/2)a} whose least positive residues (mod p) are greater than p/2.  Then,

    the Legendre Symbol   ( a

p
)  = (-1)n   

Another way to phrase Gauss' Lemma is,

    ( a

p
)  = 1 iff an even number of least positive residues of {a, 2a, 3a, ..., ((p-1)/2)a} exceed p/2.

Proof of Gauss' Lemma

Define the "absolute value" (mod p) of least positive residue, x, as

     |x| =   {

x if 0 < x < p/2,
-x if p/2 < x < p.

So, for example, |3| (mod 5) is -3, which is equivalent to 2 (mod 5).

Now let N be the product, N = a · 2a � 3a � ... � ((p-1)/2)a, so

N = a(p-1)/2 (1 � 2 � 3 � ... � ((p-1)/2),

In addition, since n counts the number of times |ka| = -ka, the product, N, can be expressed as

N = (-1)n (|a| · |2a| � |3a| � ... � |((p-1)/2)a|),

and since the values of |a|, |2a|, ..., |((p-1)/2)a| are distinct**, and they are 1, 2, ..., (p-1)/2 in some order**, then it follows that

N = (-1)n (1 � 2 � 3 � ... � ((p-1)/2),

Now, we have two formulations for N that each contain the factor (1 � 2 � 3 � ... � ((p-1)/2),

N = a(p-1)/2 (1 � 2 � 3 � ... � ((p-1)/2),
N = (-1)n (1 � 2 � 3 � ... � ((p-1)/2),

And since this factor is nonzero, we can divide through by it to obtain

a(p-1)/2 = (-1)n

which proves the result, since the left hand side is   ( a

p
)  = (-1)n   

** Comment regarding Gauss' Lemma

In the proof, I mentioned that the values of |a|, |2a|, ..., |((p-1)/2)a| are distinct, and they are 1, 2, ..., (p-1)/2 in some order, but I didn't give a reason for this (I was afraid it would bog down the flow of the proof).  So here is the justification for this step:

If |ra| = |sa|, for some r,s between 0 and p/2, then ra=±sa.  Since a is coprime to p, a has a reciprocal (mod p), i.e. some number c exists such that ac=1, then we can multiply both sides by c to get r=±s.  Since -s has no residual between 0 and p/2, r=s.

Using Gauss Lemma to prove   

( 2

p
)  =  {

1 if p≡±1 (mod 8),
-1 if p≡�3 (mod 8),

If (p-1)/2 is an even number, then the number of elements of {2, 4, ..., p-1} whose least positive residue exceeds p/2 is (p-1)/4, which is even if p≡1 (mod 8).  If (p-1)/2 is odd, then the number of elements of {2, 4, ..., p-1} whose least positive residue exceeds p/2 is (p+1)/4, which is even if  p≡-1 (mod 8).  For all other values of p, an odd number of least positive residues of {2, 4, ..., p-1} exceed p/2.

Internet references

 Wikipedia: Gauss' Lemma

Related pages in this website

Legendre symbol —  ( a

p
)  , where a is any integer, and p is an odd prime
Jacobi symbol —  ( a

n
)  , where a is any integer, and n is a positive integer greater than 2, an extension of the Legendre symbol.
Kronecker symbol —  ( a

n
)  , where a and n are any integers, an extension of the Jacobi symbol.

The webmaster and author of this Math Help site is Graeme McRae.