Euler criterion
E662761
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.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Euler criterion canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T7420184 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Euler criterion Context triple: [Legendre symbol, computableBy, Euler criterion]
-
A.
Legendre symbol
The Legendre symbol is a number-theoretic function that indicates whether an integer is a quadratic residue modulo an odd prime, taking values 1, −1, or 0 accordingly.
-
B.
Euler’s theorem
Euler’s theorem is a fundamental result in number theory stating that for any integer a coprime to n, a raised to the power of φ(n) is congruent to 1 modulo n.
-
C.
Wilson's theorem
Wilson's theorem is a result in number theory stating that a positive integer n > 1 is prime if and only if the factorial of (n − 1) is congruent to −1 modulo n.
-
D.
quadratic reciprocity law
The quadratic reciprocity law is a fundamental theorem in number theory that characterizes when a quadratic equation modulo one odd prime has solutions in terms of solvability modulo another, revealing a deep symmetry between primes.
-
E.
Fermat's little theorem
Fermat's little theorem is a fundamental result in number theory that characterizes how prime numbers interact with integer powers modulo that prime, forming the basis for many modern cryptographic algorithms.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Euler criterion Target entity description: 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.
-
A.
Legendre symbol
The Legendre symbol is a number-theoretic function that indicates whether an integer is a quadratic residue modulo an odd prime, taking values 1, −1, or 0 accordingly.
-
B.
Euler’s theorem
Euler’s theorem is a fundamental result in number theory stating that for any integer a coprime to n, a raised to the power of φ(n) is congruent to 1 modulo n.
-
C.
Wilson's theorem
Wilson's theorem is a result in number theory stating that a positive integer n > 1 is prime if and only if the factorial of (n − 1) is congruent to −1 modulo n.
-
D.
quadratic reciprocity law
The quadratic reciprocity law is a fundamental theorem in number theory that characterizes when a quadratic equation modulo one odd prime has solutions in terms of solvability modulo another, revealing a deep symmetry between primes.
-
E.
Fermat's little theorem
Fermat's little theorem is a fundamental result in number theory that characterizes how prime numbers interact with integer powers modulo that prime, forming the basis for many modern cryptographic algorithms.
- F. None of above. chosen
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 ⓘ
linked to:
Legendre symbol
|
| 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
ⓘ
Legendre symbol ⓘ modular arithmetic ⓘ modular exponentiation ⓘ multiplicative group modulo p ⓘ odd prime ⓘ quadratic non-residue ⓘ quadratic residue ⓘ |
| logicalForm | if and only if statement ⓘ |
| namedAfter | Leonhard Euler ⓘ |
| provides | practical method to compute the Legendre symbol ⓘ |
| relatedTo |
Gauss's law of quadratic reciprocity
ⓘ
linked to:
quadratic reciprocity law
Jacobi symbol ⓘ 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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Euler criterion Description of subject: 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.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.