Euler criterion

E662761

number-theoretic result theorem in number theory

Euler criterion is a number-theoretic result that characterizes quadratic residues modulo an odd prime using exponentiation, providing a practical way to evaluate the Legendre symbol.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (1)

Label	Occurrences
Euler criterion canonical	1

Statements (43)

Predicate	Object
instanceOf	number-theoretic result ⓘ theorem in number theory ⓘ
appliesTo	integer a relatively prime to p ⓘ odd prime p ⓘ
assumes	gcd(a,p)=1 ⓘ p is an odd prime ⓘ
category	results on quadratic residues ⓘ theorems about prime moduli ⓘ
characterizes	quadratic non-residues modulo an odd prime ⓘ quadratic residues modulo an odd prime ⓘ
dependsOn	Fermat's little theorem for its proof ⓘ properties of the multiplicative group modulo a prime ⓘ
doesNotApplyTo	composite moduli ⓘ
equivalentTo	(a/p) ≡ a^((p-1)/2) (mod p) where (a/p) is the Legendre symbol ⓘ
field	number theory ⓘ
hasConsequence	exactly half of the nonzero residues modulo an odd prime are quadratic residues ⓘ the Legendre symbol takes values in {−1,1} for a not divisible by p NERFINISHED ⓘ
historicalPeriod	18th century mathematics ⓘ
holdsIn	finite field of order p ⓘ
implies	the Legendre symbol is a multiplicative character of order 2 ⓘ
involvesConcept	Fermat's little theorem NERFINISHED ⓘ Legendre symbol NERFINISHED ⓘ modular arithmetic ⓘ modular exponentiation ⓘ multiplicative group modulo p ⓘ odd prime ⓘ quadratic non-residue ⓘ quadratic residue ⓘ
logicalForm	if and only if statement ⓘ
namedAfter	Leonhard Euler NERFINISHED ⓘ
provides	practical method to compute the Legendre symbol ⓘ
relatedTo	Gauss's law of quadratic reciprocity NERFINISHED ⓘ Jacobi symbol NERFINISHED ⓘ multiplicative characters modulo p ⓘ
statement	For an odd prime p and integer a with gcd(a,p)=1, a is a quadratic non-residue modulo p if and only if a^((p-1)/2) ≡ -1 (mod p). ⓘ For an odd prime p and integer a with gcd(a,p)=1, a is a quadratic residue modulo p if and only if a^((p-1)/2) ≡ 1 (mod p). ⓘ
subfield	elementary number theory ⓘ
typeOf	criterion for quadratic residuosity ⓘ
usedFor	evaluating the Legendre symbol ⓘ testing whether an integer is a quadratic residue modulo an odd prime ⓘ
usedIn	algorithms in computational number theory ⓘ primality testing methods ⓘ proofs involving quadratic residues ⓘ

Referenced by (1)

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

Legendre symbol → computableBy → Euler criterion ⓘ