# Euler's criterion

From Number

## Contents

## Statement

### In terms of quadratic residues and nonresidues

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

- is congruent to either 1 or -1 mod .
- is congruent to 1 mod if and only if is a quadratic residue mod .
- is congruent to -1 mod if and only if is a quadratic nonresidue mod .

### 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

- 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 pseudoprimes to the given base
- Euler-Jacobi primality test, which is not conclusive and can be fooled by Euler-Jacobi pseudoprimes to the given base