
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, ..., ((p1)/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, ..., ((p1)/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 � ... � ((p1)/2)a, so
N = a^{(p1)/2} (1 � 2 � 3 � ... � ((p1)/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 � ... � ((p1)/2)a),
and since the values of a, 2a, ..., ((p1)/2)a are distinct**, and they are 1, 2, ..., (p1)/2 in some order**, then it follows that
N = (1)^{n} (1 � 2 � 3 � ... � ((p1)/2),
Now, we have two formulations for N that each contain the factor (1 � 2 � 3 � ... � ((p1)/2),
N = a^{(p1)/2} (1 � 2 � 3 � ... � ((p1)/2),
N = (1)^{n} (1 � 2 � 3 � ... � ((p1)/2),
And since this factor is nonzero, we can divide through by it to obtain
a^{(p1)/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, ..., ((p1)/2)a are distinct, and they are 1, 2, ..., (p1)/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 (p1)/2 is an even number, then the number of elements of {2, 4, ..., p1} whose least positive residue exceeds p/2 is (p1)/4, which is even if p≡1 (mod 8). If (p1)/2 is odd, then the number of elements of {2, 4, ..., p1} 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, ..., p1} 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.