Euler's Criterion Explained with Worked Examples

For an odd prime and , Euler's criterion says : is a square modulo (a quadratic residue) exactly when , and a non-residue when it is .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Euler's criterion means

The Legendre symbol is if is a non-zero square mod and if not. By Fermat's little theorem , so is a square root of 1, hence ; the criterion identifies which sign. Examples with : , so 2 is a residue (indeed ); , so 3 is not. For , : , a residue since . The arithmetic uses congruences.

The computation is quick with repeated squaring, much faster than listing all squares for a large prime. The criterion also shows that exactly half of the non-zero residues are squares: the squares mod 7 are . Related facts about squares modulo small numbers are in squares modulo 4 and 8, and the powers use Euler's theorem.

The criterion leads to the law of quadratic reciprocity, quadratic reciprocity, and to primality tests. It is used with prime factorisation to decide when a quadratic congruence has a solution, compare the quadratic formula over the integers and the sum of two squares theorem.

What is it used for?

Euler criterion decides whether a number is a square modulo a prime by one power calculation.

How to use euler's criterion

  1. Compute .
  2. Compute (by repeated squaring).
  3. If the result is 1, is a quadratic residue; if , it is a non-residue.
  4. Check by listing the squares for small .

Graph

a³ mod 7 is 1 for residues and 6 (= −1) for non-residuesa = 2: 1 (residue)a = 3: 6 (non-residue)0123456701234567a³ mod 7 is 1 for residues and 6 (= −1) for non-residuesaa³ mod 7Graph with x from 0 to 7 and y from 0 to 7. Shows a³ mod 7 (6); point a = 2: 1 (residue) at (2, 1); point a = 3: 6 (non-residue) at (3, 6).

Exactly three of the six residues give 1.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: 2 modulo 7

Is 2 a square modulo 7?

Worked example
Answer
yes: 32≡2\text{yes: }3^{2}\equiv2
  1. Exponent
  2. 2³

Example 2: 3 modulo 7

Is 3 a square modulo 7?

Worked example
Answer
no\text{no}
  1. 3³

Example 3: 5 modulo 11

Is 5 a square modulo 11?

Worked example
Answer
yes: 42≡5\text{yes: }4^{2}\equiv5
  1. Exponent
  2. 5⁵

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

2 mod 7

2³ = 8 ≡ 1: a residue

Exponent (7 − 1)/2 = 3.

3 mod 7

3³ = 27 ≡ 6 ≡ −1: a non-residue

Result −1.

5 mod 11

5⁵ = 3125 ≡ 1: a residue

Exponent 5.

Squares mod 7

1, 4, 2 are residues

x² for x = 1, 2, 3.

Word problems

For an odd prime p and a not divisible by p, a^((p−1)/2) ≡ 1 (mod p) if a is a quadratic residue and ≡ −1 if it is not.

2 mod 7

Is 2 a quadratic residue mod 7?

  1. Exponent(7 − 1)/2 = 3
  2. 2³8
  3. 8 mod 71
  4. Check: 3² = 9 ≡ 2 ✓Yes.

3 mod 7

Is 3 a quadratic residue mod 7?

  1. 3³27
  2. 27 mod 76 ≡ −1
  3. Check: squares mod 7 are 1, 2, 4 ✓No.

5 mod 11 Higher

Is 5 a quadratic residue mod 11?

  1. Exponent5
  2. 5⁵ = 31253125 mod 11
  3. Result1
  4. Check: 4² = 16 ≡ 5 ✓Yes.

6 mod 13 Higher

Is 6 a quadratic residue mod 13?

  1. Exponent6
  2. 6⁶ = 46656mod 13
  3. Check: result 12 ≡ −1 ✓No.

Common mistakes

Wrong exponent

a^(p−1) ✗

a^((p−1)/2) ✓

That is Fermat’s little theorem.

Reading 6 as a residue

3³ ≡ 6 so 6 ✗

6 ≡ −1 mod 7 ✓

Interpret as −1.

Using a composite modulus

p = 9 ✗

p must be an odd prime ✓

The criterion needs a prime.

Forgetting a ≢ 0

a = 7 mod 7 ✗

a must not be divisible by p ✓

Then a^k ≡ 0.

Exam tips

  1. Exponent (p − 1)/2.
  2. 1 = residue.
  3. −1 = non-residue.
  4. p odd prime.
  5. Reduce powers step by step.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. 2^3 mod 7 Foundation

1

2. 4^3 mod 7 Foundation

1

3. 5^3 mod 7 Foundation

6

4. 3^5 mod 11 Higher

1

5. 2^5 mod 11 Higher

10

6. 7^6 mod 13 Higher

12

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Quadratic residue
A square mod p.
Euler’s criterion
a^((p−1)/2) ≡ ±1.
Legendre symbol
(a/p) = ±1.
Fermat’s little theorem
a^(p−1) ≡ 1.
Modulus
The p in mod p.
Congruence
Equal remainders.

Frequently asked questions

What is Euler’s criterion?

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

What does 1 mean?

a is a quadratic residue.

What does −1 mean?

a is a non-residue.

Is 2 a residue mod 7?

Yes.

Which page covers reciprocity?

quadratic reciprocity.

Which page covers primes?

prime factor form.

More in Discrete maths and number theory and the formula sheets.