|
|
|
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. |
Define the "absolute value" (mod p) of least positive residue, x, as
| |x| = | { |
x if 0 < x < p/2, |
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 |
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), |
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.
Wikipedia: Gauss' Lemma
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.
