Quadratic Residues and the Legendre Symbol
About this page
How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
✓ 14 results · all verified · 8 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 6 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
- Binary Operations, Monoids, Groups and Subgroups
- Cosets, Index and Lagrange's Theorem
- Cyclic Groups and Direct Products
- Group Homomorphisms and the Isomorphism Theorems
- Normal Subgroups and Quotient Groups
- Polynomial Rings, the Division Algorithm and Roots
- Rings, Subrings, Integral Domains and Fields
- The Fundamental Theorem of Finite Abelian Groups
Number Theory
Real Analysis
2 · Logical flowchart
3 · Items
Definition
Quadratic residues and nonresidues modulo an integer
Proposition
Quadratic residuosity is representative-independent and the residues are the image of squaring
Corollary
A coprime exponent gives a unique nonzero k-th root modulo a prime
Theorem
The nonzero squares modulo an odd prime form an index-two subgroup
Theorem
An odd prime has (p-1)/2 nonzero quadratic residues and as many nonresidues
Definition
The Legendre symbol, including its zero value
Proposition
The Legendre symbol is well defined on residue classes
Proposition
On the units, the Legendre symbol is the unique nontrivial homomorphism to {±1}
Theorem
Euler's criterion: (a/p)≡ a^(p-1)/2 (mod p)
Theorem
The Legendre symbol is multiplicative for all integer numerators
Corollary
x²≡ a (mod p) has exactly 1+(a/p) solution classes
Corollary
The discriminant counts roots of Ax²+Bx+C≡0 (mod p) for odd prime p∤ A
Lemma
Multiplication by a with p∤ a permutes an odd prime's signed half-system up to sign
Theorem
Gauss's quadratic-residue lemma
Theorem
First supplement: (-1/p)=(-1)^(p-1)/2
Theorem
Second supplement: (2/p)=(-1)^(p²-1)/8
Sources
- H. Hackman, Elementary Number Theory, Chapter D, Section D.I
- W. Stein, Elementary Number Theory, Section 4.1
- A. Gorodnik, Number Theory, Lecture 9, Section 1
- N. Mascot, Legendre Symbols and Quadratic Reciprocity, Chapter 3
- W. Stein, Elementary Number Theory, Section 4.2
- A. Gorodnik, Number Theory, Lecture 9, Theorem 1.5
- A. Gorodnik, Number Theory, Lecture 9, Theorem 1.6
- W. Stein, Elementary Number Theory, Corollary 4.2.3
- H. Hackman, Elementary Number Theory, Chapter D, Section D.IV
- W. Stein, Elementary Number Theory, Section 4.3
- W. Stein, Elementary Number Theory, Lemma 4.3.1
- W. Stein, Elementary Number Theory, Theorem 4.1.7
- H. Hackman, Elementary Number Theory, Chapter D, Sections D.I and D.IV