I learned a very elegant proof of Gauss' Lemma from number theory, which asserts that the Legendre Symbol (a/p) is equivalent to (-1)^μ, where μ represents the number of least negative residues modulo p.
I think the proof is elegant because it focused on the construction of a very discreet yet useful set, and utilizes quite a few techniques to finally reach a conclusion, via some very epic deductions.
Here's the proof as I understand it.
The assertion is that (a/p)=(-1)^μ.
We begin by constructing the set S={m, 2m, 3m,..., Nm}, where N=(p-1)/2 (an integer), and gcd(m,p)=1. We then construct another set T from S, elements of which are those in S, but reduced modulo p, so they would be confined within the open interval (-p/2, p/2).
We will determine 3 properties of T that will be used later in the proof. First note that for all t_i and t_j in T, they will be incongruent modulo p. This is because, returning to S, we noticed that gcd(m,p)=1, and we can immediately see that any reduction of elements from S, all of which are inequivalent, will still yield different elements in T. Next, it's obvious that all t_i will be nonzero, because none of the elements in S can possibly be multiples of p, as gcd(m,p)=1.
Finally, we make the statement that for t_1 and t_2 in T, t_1≠-t_2. This is seemingly not motivated, but it will be of use later. We first assume that t_1=-t_2, so that t_1+t_2=0. This implies that - since every t_i is a result of reduction modulo p from some element s_i - there exist some elements s_1 and s_2 that are the sum of t_1 and some multiple of p and t_2 and some multiple of p respectively. (Because reducing modulo p means subtracting - or in some cases adding - multiples of p) This we see that s_1+s_2=kp, for some integer k, or that s_1+s_2 is some multiple of p. Returning to the definition of elements of S, if s_1 and s_2 are in S, then they may be written as some coefficient j_1 and j_2, each multiplied by some m. Thus we have that mj_1+mj_2=kp or (j_1+j_2)m=kp. However, if we look at the restrictions on j_i or the coefficients of m in S, we see that the maximum value for j_i is (p-1)/2. Even with j_1=j_2=(p-1)/2, so that j_1+j_2=2[(p-1)/2]=p-1, it is impossible for (j_1+j_2)m=kp to be true, as the LHS never exceeds as a multiple or even meets p. Thus t_1≠-t_2.
Ok. Continuing from here, after establishing these three properties, we are prepared to understand the characteristics of T. If we consider all positive elements to be T, then we could have the integer elements on the open interval (0, p/2) or {1, 2, 3,..., N}. (recall that N=(p-1)/2) It satisfied all three preestablished properties of T, and |{1, 2, 3,..., N}|=|S|=(p-1)/2, so it works. Now we consider the general case on the interval (-p/2, p/2). If there are only (p-1)/2 elements in T, non-inclusive, and no element can be the inverse of itself, it must be the set T={±1, ±2, ±3,..., ±N}.
With this in consideration, we can now move toward the finish. We multiply all s_i and set it congruent to the multiplication of all t_i modulo p, so prod(t_i)≡prod(s_i) (mod p). Thus we see that (±1)(±2)(±3)•...•(±N)≡(m)(2m)(3m)•...•(Nm) (mod p). Notice that since all coefficients are relatively prime to the modulus, we can cancel all integers ranging from 1 to N, so that (±1)(±1)(±1)•...•(±1)≡(m)(m)(m)•...•(m) (mod p). Now, how many m are there? Well, S ranged from 1 to N, so there must be exactly N m's. Thus, we have that (±1)(±1)(±1)•...•(±1)≡m^{(p-1)/2} (mod p). Now, what may the LHS of this congruence be? Well, in the beginning of the proof, we defined μ to be the number of least negative residues modulo p. We can then say that the value of that long chain of ±1s can be expressed as (-1)^μ, where μ is the number of elements from T that are negative, hence 'least' - coming from the notion that they are absolutely reduced - 'negative residues modulo p'.
Recalling Euler's Criterion, which asserts that a^{(p-1)/2} ≡(a/p) (mod p) for some a (which is inexpressibly far easier to prove), we can then write that (a/p)≡(-1)^μ (mod p). However, there is one final step; notice that both LHS and RHS are binary, as they can either be 1 or -1. Thus, the modulo p is unnecessary, as it does not change the result, so we must have that (a/p)=(-1)^μ, which is what we wanted to prove.
QED
Anyway, yes, I thought this proof was cool, and that's what I have learned this week so far.
