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:
“O, popular applause! what heart of man
Is proof against thy sweet, seducing charms?”
—William Cowper (1731–1800)
“The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)
“If some books are deemed most baneful and their sale forbid, how, then, with deadlier facts, not dreams of doting men? Those whom books will hurt will not be proof against events. Events, not books, should be forbid.”
—Herman Melville (1819–1891)