Number theory Quadratic residues and reciprocity Lemma

Gauss's lemma on quadratic residues

Statement

Let $p$ be an odd prime and let $a$ be an integer with $p \nmid a$ . Reduce each of the integers $a, 2a, \dots, \frac{p-1}{2} a$ to its least positive residue modulo $p$ . Let $n$ be the number of these residues that are greater than $p/2$ . Then $\left(\frac{a}{p}\right) = (-1)^n$ , where the left side is the Legendre symbol.

Remarks

For example, take $p = 7$ and $a = 3$ . The residues of $3, 6, 9$ are $3, 6, 2$ , and only $6$ is greater than $7/2$ . So $\left(\frac{3}{7}\right) = -1$ . With $a = 2$ , the lemma gives the second supplement to quadratic reciprocity. Gauss used the lemma in one of his proofs of the law of quadratic reciprocity.

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Divisibility definition
Congruence modulo n definition
Prime number definition
Quadratic residue definition
Legendre symbol definition
Gauss's lemma on quadratic residues statement

Where this leads

1 page builds on this one.

Eisenstein's lemma

Tag	`037ACYXB5Z`
URI	`m2://037ACYXB5Z`
Aliases	`gauss-lemma`
Kind	statement, lemma
Writing	W0 stub
MSC	11A15
Status	This copy of the site has no build data. Run `m2 status 037ACYXB5Z`.
Uses	Legendre symbol
Same as	Wikidata Q2526246 Wikipedia Gauss's lemma (number theory)

Gauss's lemma on quadratic residues

Statement

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by