Euler's criterion

In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, 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 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 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, x2 ≡ 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, ( p − x ) 2 ≡ x 2 ( mod p ) . {displaystyle (p-x)^{2}equiv x^{2}{pmod {p}}.} This is because ( p − x ) 2 ≡ p 2 − 2 x p + x 2 ≡ x 2 ( mod p ) . {displaystyle (p-x)^{2}equiv p^{2}-{2}{x}{p}+x^{2}equiv x^{2}{pmod {p}}.} So, the p − 1 2 {displaystyle { frac {p-1}{2}}} distinct quadratic residues are: 1 2 , 2 2 , . . . , ( p − 1 2 ) 2 ( ( mod p ) ) {displaystyle 1^{2},2^{2},...,({ frac {p-1}{2}})^{2}({pmod {p}})} As a is coprime to p, Fermat's little theorem says that