Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Euler's criterion
Summary
In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let p be an odd prime and a be an integer coprime to p. Then
Euler's criterion can be concisely reformulated using the Legendre symbol:
The criterion first appeared in a 1748 paper by Leonhard Euler.
The proof uses the fact that the residue classes modulo a prime number are a field. See the article prime field for more details.
Because the modulus is prime, Lagrange's theorem applies: a polynomial of degree k can only have at most k roots. In particular, x^2 ≡ a (mod p) has at most 2 solutions for each a. This immediately implies that besides 0 there are at least p − 1/2 distinct quadratic residues modulo p: each of the p − 1 possible values of x can only be accompanied by one other to give the same residue.
In fact, This is because
So, the distinct quadratic residues are:
As a is coprime to p, Fermat's little theorem says that
which can be written as
Since the integers mod p form a field, for each a, one or the other of these factors must be zero.
Now if a is a quadratic residue, a ≡ x2,
So every quadratic residue (mod p) makes the first factor zero.
Applying Lagrange's theorem again, we note that there can be no more than p − 1/2 values of a that make the first factor zero. But as we noted at the beginning, there are at least p − 1/2 distinct quadratic residues (mod p) (besides 0). Therefore, they are precisely the residue classes that make the first factor zero. The other p − 1/2 residue classes, the nonresidues, must make the second factor zero, or they would not satisfy Fermat's little theorem. This is Euler's criterion.
This proof only uses the fact that any congruence has a unique (modulo ) solution provided does not divide . (This is true because as runs through all nonzero remainders modulo without repetitions, so does - if we have , then , hence , but and aren't congruent modulo .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.