Gauss’s lemma in number theory

E29548

lemma in number theory result in elementary number theory

Gauss’s lemma in number theory is a result that relates the Legendre symbol to the number of sign changes in a certain sequence of multiples, providing a practical criterion for determining quadratic residues modulo an odd prime.

Jump to: Surface forms Statements Referenced by

Observed surface forms (3)

Surface form	Occurrences
Gauss’s lemma (number theory)	0
Euler’s criterion	1
Legendre symbol takes values ±1 for a coprime to p	1

Statements (44)

Predicate	Object
instanceOf	lemma in number theory ⓘ result in elementary number theory ⓘ
appearsIn	Disquisitiones Arithmeticae ⓘ surface form: Gauss’s Disquisitiones Arithmeticae
appliesTo	odd prime modulus ⓘ
assumes	a is an integer coprime to p ⓘ p is an odd prime ⓘ
category	results about quadratic residues ⓘ theorems about primes ⓘ
characterizes	quadratic non-residues via parity of negative multiples ⓘ quadratic residues via parity of negative multiples ⓘ
concerns	quadratic non-residues modulo an odd prime ⓘ quadratic residues modulo an odd prime ⓘ
domain	modular arithmetic ⓘ
equates	Legendre symbol (a\|p) with (−1)^n ⓘ
equivalentTo	certain combinatorial formulations of the Legendre symbol ⓘ
excludes	case where p divides a ⓘ
field	number theory ⓘ
gives	criterion for quadratic residuosity modulo an odd prime ⓘ
hasNotation	(a\|p) for the Legendre symbol in its statement ⓘ
historicalPeriod	early 19th century ⓘ
holdsFor	integers a with gcd(a,p)=1 ⓘ
implies	Gauss’s lemma in number theory self-linksurface differs ⓘ surface form: Legendre symbol takes values ±1 for a coprime to p
involves	counting negative representatives among reduced multiples ⓘ sequence of multiples a,2a,…,((p−1)/2)a modulo p ⓘ
namedAfter	Carl Friedrich Gauss ⓘ
oftenFormulatedWith	interval (−p/2,p/2] for representatives modulo p ⓘ
provides	practical method to compute Legendre symbols ⓘ
relatedTo	Gauss’s lemma in number theory self-linksurface differs ⓘ surface form: Euler’s criterion quadratic reciprocity law ⓘ
relates	Legendre symbol ⓘ number of sign changes in a sequence of multiples ⓘ
requires	reduction of integers modulo p into a symmetric interval around 0 ⓘ
statement	Let p be an odd prime and a an integer coprime to p. Consider the numbers a,2a,3a,…,((p−1)/2)a reduced modulo p into the interval (−p/2,p/2]. Let n be the number of these residues that are negative. Then (a\|p) = (−1)^n, where (a\|p) is the Legendre symbol. ⓘ
subfield	elementary number theory ⓘ quadratic number theory ⓘ
toolIn	computational number theory ⓘ
topic	Legendre symbol ⓘ quadratic residues ⓘ
typeOf	criterion for quadratic residuosity ⓘ
usedBy	elementary number theory textbooks ⓘ
usedFor	computing Legendre symbols ⓘ testing whether an integer is a quadratic residue modulo an odd prime ⓘ
usedIn	elementary proofs of properties of Legendre symbols ⓘ proofs of quadratic reciprocity ⓘ

Referenced by (3)

Full triples — surface form annotated when it differs from this entity's canonical label.

Carl Friedrich Gauss → hasConceptNamedAfter → Gauss’s lemma in number theory ⓘ

Gauss’s lemma in number theory → implies → Gauss’s lemma in number theory self-linksurface differs ⓘ

subject surface form: Gauss’s lemma (number theory)

this entity surface form: Legendre symbol takes values ±1 for a coprime to p

Gauss’s lemma in number theory → relatedTo → Gauss’s lemma in number theory self-linksurface differs ⓘ

subject surface form: Gauss’s lemma (number theory)

this entity surface form: Euler’s criterion