Difference between revisions of "Euler's criterion"

From Number
Jump to: navigation, search
(Created page with "==Statement== ===In terms of quadratic residues and nonresidues=== Suppose <math>p</math> is an odd prime number. Consider an integer <math>a</math> that is not zero mod...")
 
(Related facts)
 
(2 intermediate revisions by the same user not shown)
Line 16: Line 16:
  
 
where the expression on the right side is the [[Legendre symbol]], defined to be <math>+1</math> for a [[quadratic residue]] and <math>-1</math> for a [[quadratic nonresidue]]. Note that the Legendre symbol is the restriction to primes of the [[Jacobi symbol]].
 
where the expression on the right side is the [[Legendre symbol]], defined to be <math>+1</math> for a [[quadratic residue]] and <math>-1</math> for a [[quadratic nonresidue]]. Note that the Legendre symbol is the restriction to primes of the [[Jacobi symbol]].
 +
 +
==Related facts==
 +
 +
===Applications===
 +
 +
* [[Congruence condition for minus one to be a quadratic residue]]
 +
* [[Congruence condition for two to be a quadratic residue]]
 +
* [[Quadratic reciprocity]]
 +
 +
===Primality tests===
 +
 +
* [[Euler primality test]], which is not conclusive and can be fooled by [[Euler pseudoprime]]s to the given base
 +
* [[Euler-Jacobi primality test]], which is not conclusive and can be fooled by [[Euler-Jacobi pseudoprime]]s to the given base

Latest revision as of 20:19, 2 January 2012

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