Euler's criterion

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

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 k2a (mod p)), then

a(p − 1)/2 ≡ 1 (mod p)

and if a is not a quadratic residue modulo p then

a(p − 1)/2 ≡ −1 (mod p).

Additionally, the Legendre symbol can be used to define Euler's criterion. Euler proved that

<math>

\left(\frac{a}{p}\right) \equiv a^{\left(\frac{p-1}{2}\right)}\pmod p <math>

Proof of Euler's criterion

In one case, we assume a is a quadratic residue modulo p. We find k such that k2a (mod p). Then a(p − 1)/2 = kp − 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 k2 = αia (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 = 171 ≡ 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 = 176 ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 22 = 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:

12 = 1
22 = 4
32 = 9
42 = 16
52 = 25 ≡ 8 (mod 17)
62 = 36 ≡ 2 (mod 17)
72 = 49 ≡ 15 (mod 17)
82 = 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 92 = (−8)2 = 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 = 28 ≡ 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 = 38 = 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.

sv:Eulers kriterium

Navigation

  • Art and Cultures
    • Art (https://academickids.com/encyclopedia/index.php/Art)
    • Architecture (https://academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (https://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (https://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools