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 we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)
“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)
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)