Discover

In mathematics, 'Euler's criterion' is used in determining in number theory whether a given integer is a quadratic residue modulo a prime.

Contents

Definition

Proof of Euler's criterion

Examples

Definition

If ''p'' is an odd prime and ''a'' is an integer coprime to ''p'' then Euler's criterion states:
if ''a'' is quadratic residue modulo ''p'' (i.e. there exists a number ''k'' such that ''k''² ≡ ''a'' (mod ''p'')), then
:$a^\{(p\; -\; 1)\; /\; 2\}\; equiv\; 1\; pmod\; p$
and if ''a'' is not a quadratic residue modulo ''p'' then
:$a^\{(p\; -\; 1)/2\}\; equiv\; -1\; pmod\; p$
Euler's criterion can be concisely reformulated using the Legendre symbol:
:$$
left(rac{a}{p}
ight) equiv a^{(p-1)/2} pmod p

Proof of Euler's criterion

In one case, we assume ''a'' is a quadratic residue modulo ''p''. We find ''k'' such that ''k''² ≡ ''a'' (mod ''p''). Then ''a''^{(''p'' − 1)/2} = ''k''^{''p'' − 1} ≡ 1 (mod ''p'') by Fermat's little theorem.
In the other case, we assume ''a''^{(''p'' − 1)/2} ≡ 1 (mod ''p''). Then let α be a primitive element modulo ''p'', that is to say ''a'' = α^''i''. So, α^{''i''(''p'' − 1)/2} ≡ 1 (mod ''p''). By Fermat's little theorem, (''p'' − 1) divides ''i''(''p'' − 1)/2, so ''i'' must be even. Let ''k'' ≡ α^''i''/2 (mod ''p''). We finally have ''k''² = α^''i'' ≡ ''a'' (mod ''p'').

Examples

'Example 1: Finding primes for which ''a'' is a residue'
Let ''a'' = 17. For which primes ''p'' is 17 a quadratic residue?
We can test prime ''p's manually given the formula above.
In one case, testing ''p'' = 3, we have 17^{(3 − 1)/2} = 17¹ ≡ 2 (mod 3) ≡ -1 (mod 3), therefore 17 is not a quadratic residue modulo 3.
In another case, testing ''p'' = 13, we have 17^{(13 − 1)/2} = 17⁶ ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 2² = 4.
We can do these calculations faster by using various modular arithmetic and Legendre symbol properties.
If we keep calculating the values, we find:
:(17/''p'') = +1 for ''p'' = {13, 19, ...} (17 is a quadratic residue modulo these values)
:(17/''p'') = −1 for ''p'' = {3, 5, 7, 11, 23, ...} (17 is not a quadratic residue modulo these values)
'Example 2: Finding residues given a prime modulus ''p'' '
Which numbers are squares modulo 17 (quadratic residues modulo 17)?
We can manually calculate:
: 1² = 1
: 2² = 4
: 3² = 9
: 4² = 16
: 5² = 25 ≡ 8 (mod 17)
: 6² = 36 ≡ 2 (mod 17)
: 7² = 49 ≡ 15 (mod 17)
: 8² = 64 ≡ 13 (mod 17)
So the set of the quadratic residues modulo 17 is {1,2,4,8,9,13,15,16}. Note that we did not need to calculate squares for the values 9 through 16, as they are all negatives of the previously squared values (e.g. 9 ≡ −8 (mod 17), so 9² = (−8)² = 64 ≡ 13 (mod 17)).
We can find quadratic residues or verify them using the above formula. To test if 2 is a quadratic residue modulo 17, we calculate 2^{(17 − 1)/2} = 2⁸ ≡ 1 (mod 17), so it is a quadratic residue. To test if 3 is a quadratic residue modulo 17, we calculate 3^{(17 − 1)/2} = 3⁸ = 16 ≡ -1 (mod 17), so it is not a quadratic residue.
Euler's criterion is related to the Law of quadratic reciprocity and is used in a definition of Euler-Jacobi pseudoprimes.