Consider the Legendre Symbols and ;

The symbol is completely multiplicative so .

We want to prove that the number of Legendre symbols taking on value is odd.

If it is not, however, then one side of the previous equality will be while the other side will be ... contradiction. We can have e.g. and so = 1, etc.

Why is the Legendre symbol multiplicative? This property follows from Euler's Criterion, which states that . This is proven essentially by writing where is a primitive root and is even iff is a quadradic residue and using Fermat's little theorem.