2 mod 7
2³ = 8 ≡ 1: a residue
Exponent (7 − 1)/2 = 3.
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 .
This page is easier if you are comfortable with:
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.
Euler criterion decides whether a number is a square modulo a prime by one power calculation.
Exactly three of the six residues give 1.
These examples are worked by hand, step by step, so you can compare your own working.
Is 2 a square modulo 7?
Is 3 a square modulo 7?
Is 5 a square modulo 11?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
2³ = 8 ≡ 1: a residue
Exponent (7 − 1)/2 = 3.
3³ = 27 ≡ 6 ≡ −1: a non-residue
Result −1.
5⁵ = 3125 ≡ 1: a residue
Exponent 5.
1, 4, 2 are residues
x² for x = 1, 2, 3.
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.
Is 2 a quadratic residue mod 7?
Is 3 a quadratic residue mod 7?
Is 5 a quadratic residue mod 11?
Is 6 a quadratic residue mod 13?
a^(p−1) ✗
a^((p−1)/2) ✓
That is Fermat’s little theorem.
3³ ≡ 6 so 6 ✗
6 ≡ −1 mod 7 ✓
Interpret as −1.
p = 9 ✗
p must be an odd prime ✓
The criterion needs a prime.
a = 7 mod 7 ✗
a must not be divisible by p ✓
Then a^k ≡ 0.
Try each one on paper, then open the answer. Use the solver above to see the full working.
1
1
6
1
10
12
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
a^((p−1)/2) ≡ (a/p) mod p.
a is a quadratic residue.
a is a non-residue.
Yes.
quadratic reciprocity.
prime factor form.
More in Discrete maths and number theory and the formula sheets.