Proof
In general, for any finite group G of order n, it is easy to determine the signature of the permutation πg made by left-multiplication by the element g of G. The permutation πg will be even, unless there are an odd number of orbits of even size. Assuming n even, therefore, the condition for πg to be an odd permutation, when g has order k, is that n/k should be odd, or that the subgroup <g> generated by g should have odd index.
We will apply this to the group of nonzero numbers mod p, which is a cyclic group of order p − 1. The jth power of a primitive root modulo p will by index calculus have index the greatest common divisor
- i = (j, p − 1).
The condition for a nonzero number mod p to be an quadratic non-residue is to be an odd power of a primitive root. The lemma therefore comes down to saying that i is odd when j is odd, which is true a fortiori, and j is odd when i is odd, which is true because p − 1 is even (p is odd).
Read more about this topic: Zolotarev's Lemma
Famous quotes containing the word proof:
“If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
—Susan B. Anthony (1820–1906)
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“To cease to admire is a proof of deterioration.”
—Charles Horton Cooley (1864–1929)