Quadratic Reciprocity Explained with Worked Examples

For distinct odd primes and , . The two symbols are equal unless both primes are , in which case they are opposite.

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 Quadratic reciprocity means

The symbol says whether is a square modulo , found with Euler's criterion. The law lets us flip to with a modulus that is smaller after reduction. Examples: , , both , so the product is : (squares mod 7 are 1, 2, 4) and , product .

For , (both ) the product is : (squares mod 13: 1, 3, 4, 9, 10, 12) and (squares mod 5: 1, 4), product . For , (both ): : , . The remainders mod 4 are as in squares modulo 4 and 8.

Quadratic reciprocity, Gauss's "golden theorem", gives a fast algorithm for deciding whether is solvable, together with the rules for and . It is used in primality testing and cryptography (Chinese remainder theorem, prime factors) and in the study of which primes are sums of two squares; see also linear congruences.

What is it used for?

Quadratic reciprocity relates whether p is a square mod q with whether q is a square mod p.

How to use quadratic reciprocity

  1. Check that and are distinct odd primes.
  2. Compute the sign : if both are , otherwise .
  3. Use it to turn into .
  4. Reduce the top modulo the bottom and repeat.

Graph

Product of the two symbols for the pairs (3,7), (5,13), (7,11)(3,7): −1(5,13): +1(7,11): −100.511.522.533.54-1.5-1-0.500.511.5Product of the two symbols for the pairs (3,7), (5,13), (7,11)pairproductGraph with x from 0 to 4 and y from -1.5 to 1.5. Shows product of symbols (3); point (3,7): −1 at (1, -1); point (5,13): +1 at (2, 1); point (7,11): −1 at (3, -1).

The product is −1 exactly when both primes are 3 mod 4.

Worked examples

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

Example 1: 3 and 7

Find .

Worked example Answer checked
Answer
−1-1
  1. Both ≡ 3 mod 4
  2. Check

Example 2: 5 and 13

Find .

Worked example Answer checked
Answer
11
  1. Both ≡ 1 mod 4
  2. Check

Example 3: 7 and 11

Find .

Worked example Answer checked
Answer
−1-1
  1. Both ≡ 3 mod 4
  2. Check

Special cases

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

(3/7)

3 ≡ 3 and 7 ≡ 3 mod 4: (3/7) = −(7/3) = −(1/3) = −1

Both ≡ 3 mod 4, so flip sign.

(5/11)

5 ≡ 1 mod 4: (5/11) = (11/5) = (1/5) = 1

One ≡ 1 mod 4: no sign change.

(2/7)

second supplement: p ≡ ±1 mod 8 → +1

7 ≡ −1 mod 8.

(−1/p)

= (−1)^((p−1)/2)

p = 7: −1.

Word problems

For distinct odd primes p, q: (p/q)(q/p) = (−1)^((p−1)/2 · (q−1)/2). So (p/q) = (q/p) unless both are ≡ 3 mod 4, in which case (p/q) = −(q/p).

(3/7)

Evaluate (3/7).

  1. Both ≡ 3 mod 4flip sign
  2. (7/3)(1/3) = 1
  3. Result−1
  4. Check: 3³ mod 7 = 6 ≡ −1 ✓−1.

(5/11)

Evaluate (5/11).

  1. 5 ≡ 1 mod 4no flip
  2. (11/5)(1/5) = 1
  3. Check: 5⁵ mod 11 = 1 ✓+1.

(7/19) Higher

Evaluate (7/19).

  1. Both ≡ 3 mod 4flip
  2. (19/7)(5/7) = −1
  3. Result+1
  4. Check: 7⁹ mod 19 = 1 ✓+1.

(−1/13) Higher

Evaluate (−1/13).

  1. (−1)^61
  2. Check: ✓+1.

Common mistakes

Flipping the sign always

(5/11) = −(11/5) ✗

flip only when both ≡ 3 mod 4 ✓

Check both residues.

Forgetting to reduce

(11/5) left as is ✗

(11/5) = (1/5) ✓

Reduce 11 mod 5.

Using composite moduli

(a/9) ✗

p must be an odd prime ✓

Use Jacobi symbols otherwise.

Mixing up the supplement

(2/p) = 1 for p ≡ 3 mod 8 ✗

(2/p) = −1 ✓

p ≡ ±3 mod 8 gives −1.

Exam tips

  1. Reduce first.
  2. Both ≡ 3 mod 4: flip.
  3. Use the supplements for 2 and −1.
  4. Check with Euler.
  5. Odd primes only.

Practice questions

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

1. (3/5): 3^2 mod 5 Foundation

4

2. (2/5): 2^2 mod 5 Foundation

4

3. (4/7): 4^3 mod 7 Foundation

1

4. (5/7): 5^3 mod 7 Higher

6

5. 11 mod 4 Higher

3

6. (−1)^((13−1)/2) Higher

1

Practice generator

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

Solve: …

Key terms

Legendre symbol
(a/p) = 1, −1 or 0.
Quadratic reciprocity
Relates (p/q) and (q/p).
Residue
A square mod p.
Supplementary law
Rule for (−1/p) and (2/p).
Odd prime
A prime other than 2.
Jacobi symbol
Generalises to odd moduli.

Frequently asked questions

What does quadratic reciprocity say?

(p/q)(q/p) = (−1)^(((p−1)/2)((q−1)/2)).

When is there a sign change?

When both primes are ≡ 3 mod 4.

What is (−1/p)?

1 if p ≡ 1 mod 4, else −1.

What is (2/p)?

1 if p ≡ ±1 mod 8.

Which page covers Euler’s criterion?

Euler’s criterion.

Which page covers Möbius inversion?

Möbius inversion.

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