Proof
A fairly simple proof of the lemma, reminiscent of one of the simplest proofs of Fermat's little theorem, can be obtained by evaluating the product
modulo p in two different ways. On one hand it is equal to
The second evaluation takes more work. If x is a nonzero residue modulo p, let us define the "absolute value" of x to be
Since n counts those multiples ka which are in the latter range, and since for those multiples, −ka is in the first range, we have
Now observe that the values |ra| are distinct for r = 1, 2, ..., (p−1)/2. Indeed, if |ra| = |sa|, then ra = ±sa, and therefore r = ±s (because a is invertible modulo p), so r = s because they are both in the range 1 ≤ r ≤ (p−1)/2. But there are exactly (p−1)/2 of them, so they must just be some rearrangement of the integers 1, 2, ..., (p−1)/2. Therefore
Comparing with our first evaluation, we may cancel out the nonzero factor
and we are left with
This is the desired result, because by Euler's criterion the left hand side is just an alternative expression for the Legendre symbol (a/p).
Read more about this topic: Gauss's Lemma (number Theory)
Famous quotes containing the word proof:
“He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
—Herman Melville (1819–1891)
“If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
—Thomas Jefferson (1743–1826)
“It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
—William Shakespeare (1564–1616)