Euler's criterion

From Number
Revision as of 20:19, 2 January 2012 by Vipul (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Statement

In terms of quadratic residues and nonresidues

Suppose is an odd prime number. Consider an integer that is not zero mod . Then:

In terms of Legendre symbol

Suppose is an odd prime number. Consider an integer that is not zero mod . Then:

where the expression on the right side is the Legendre symbol, defined to be for a quadratic residue and for a quadratic nonresidue. Note that the Legendre symbol is the restriction to primes of the Jacobi symbol.

Related facts

Applications

Primality tests