Gauss's Lemma

    

Proposition (Gauss's Lemma) Let be an odd prime with If is the number of least positive residues of the integers that exceed then
    Proof. Let be those least positive residues of that exceed , and be those least positive residues of that do not exceed It follows that



is a permutation of the set [[show it]] and so  



Simplifying with modulus we have



By definition of the and we know,







By appealing to Euler's Criterion.



as desired.

Example (Gauss's Lemma) Find and by using Gauss's Lemma.
    Solution. Since we look at the first 6 multiples of 7 namely: The least positive residues are The number of them that exceed is 3 namely: Therefore,
    Since we look at the first 26 multiples of 9 (mod 53) namely

    

The number of them that exceed is 12. Therefore,      

Proposition (Quadratic Character of 2) If is an odd prime, then



    Proof. Applying Gauss's Lemma, we look at the first multiples of namely These positive integers are all less than and so they are their own least positive residues modulo Let denote the set of least positive residues that exceed as in Gauss's lemma. Since is odd one of the follow cases must hold.

for

for

for



In the first two cases the number of elements in is even and so when In the last two cases the number of elements in is odd and so when   Finally, because is even when and   odd when it follows that as desired.

• print this page
• pages linking here
• related pages

Cite this as:
Gauss Lemma
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/gauss-lemma.html