Editing Euler's criterion (section)

==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<sup>(3 − 1)/2</sup> = 17<sup>1</sup> ≡ 2 ≡ −1 (mod 3), therefore 17 is not a quadratic residue modulo 3.

In another case, testing ''p'' = 13, we have 17<sup>(13 − 1)/2</sup> = 17<sup>6</sup> ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13.  As confirmation, note that 17 ≡ 4 (mod 13), and 2<sup>2</sup> = 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 it as:
: 1<sup>2</sup> = 1
: 2<sup>2</sup> = 4
: 3<sup>2</sup> = 9
: 4<sup>2</sup> = 16
: 5<sup>2</sup> = 25 ≡ 8 (mod 17)
: 6<sup>2</sup> = 36 ≡ 2 (mod 17)
: 7<sup>2</sup> = 49 ≡ 15 (mod 17)
: 8<sup>2</sup> = 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<sup>2</sup> ≡ (−8)<sup>2</sup> = 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<sup>(17 − 1)/2</sup> = 2<sup>8</sup> ≡ 1 (mod 17), so it is a quadratic residue.  To test if 3 is a quadratic residue modulo 17, we calculate 3<sup>(17 − 1)/2</sup> = 3<sup>8</sup> ≡ 16 ≡ −1 (mod 17), so it is not a quadratic residue.

Euler's criterion is related to the [[Quadratic reciprocity|law of quadratic reciprocity]].