Quadratic residues ask a simple-looking question with deep algorithmic consequences: when does the congruence x²≡a (mod n) have a solution, and how can that solution be found efficiently?

Squares modulo an integer behave very differently from ordinary squares over the integers. Modulo a prime p, only about half of the nonzero residues are squares. The Legendre symbol compresses that yes/no information. Euler’s criterion turns it into a fast exponentiation test. Quadratic reciprocity allows difficult symbols to be transformed into easier ones. And when a square root actually exists modulo an odd prime, algorithms such as Tonelli–Shanks recover it without searching every residue.

This is Guide 5 in the Bukit Timah Tutor Computational Number Theory series. Use the BTT Mathematics Hub for the wider Mathematics route.

Existence test → symbol calculation → theorem reduction → root algorithm → verification.

1. Quadratic residues modulo a prime

Let p be an odd prime. A nonzero residue a modulo p is called a quadratic residue if there exists an x with x²≡a (mod p). Otherwise a is a quadratic nonresidue.

For p=13, the nonzero squares are obtained from 1² through 6² because x and −x have the same square:

1² ≡ 1
2² ≡ 4
3² ≡ 9
4² ≡ 3
5² ≡ 12
6² ≡ 10   (mod 13)

Thus the nonzero quadratic residues modulo 13 are {1,3,4,9,10,12}. Exactly six of the twelve nonzero residue classes are squares.

2. Why exactly half the nonzero residues are squares

Consider the map x↦x² on the nonzero residues modulo p. If x²≡y², then p divides (x−y)(x+y). Because p is prime, x≡y or x≡−y. So every nonzero square has exactly two square roots, x and −x.

There are p−1 nonzero inputs and they pair into {x,−x}. Hence there are (p−1)/2 distinct nonzero quadratic residues.

3. The Legendre symbol

For an odd prime p, the Legendre symbol is defined by

(a/p) =  0  if p divides a
         1  if a is a nonzero quadratic residue mod p
        −1  if a is a quadratic nonresidue mod p.

This one symbol records exactly the information needed to decide whether x²≡a (mod p) can have a nonzero solution.

It is multiplicative:

(ab/p)=(a/p)(b/p).

That property lets a difficult residue be broken into simpler factors.

4. Euler’s criterion

Euler’s criterion gives a direct computational test. For p odd prime and p∤a,

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

So the modular power must be 1 if a is a quadratic residue and −1≡p−1 if a is a nonresidue.

Example: is 10 a square modulo 13?

Compute 10^6 mod 13. Since 10²≡9, 10⁴≡3 and 10⁶≡3·9≡27≡1. Therefore (10/13)=1 and a square root exists. Indeed 6²=36≡10 and 7²=49≡10.

5. Euler’s criterion from group structure

If a=x² is a nonzero square, then

a^((p−1)/2) = x^(p−1) ≡ 1 (mod p)

by Fermat’s little theorem. The deeper fact is that the polynomial y²−1 has only the roots ±1 modulo p, so every nonzero a has half-power equal to one of those values. Exactly half of the residues produce 1 and half produce −1.

6. The supplementary laws

Two special Legendre symbols occur constantly.

(−1/p)=1 if p≡1 (mod 4), and −1 if p≡3 (mod 4).

This decides when −1 has a square root modulo p.

(2/p)=1 if p≡±1 (mod 8), and −1 if p≡±3 (mod 8).

These compact congruence rules eliminate many exponentiations.

7. Quadratic reciprocity

For distinct odd primes p and q, quadratic reciprocity states

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

Equivalently, (p/q)=(q/p) unless both p and q are congruent to 3 modulo 4, in which case the sign flips.

The theorem is powerful computationally because it allows a large numerator to become a smaller one after swapping and reducing.

Example: evaluate (19/43)

Since 19≡3 mod 4 and 43≡3 mod 4, reciprocity introduces a minus sign:

(19/43)=−(43/19)=−(5/19).

Now 5≡1 mod 4, so (5/19)=(19/5)=(4/5)=1. Hence (19/43)=−1.

8. A Euclidean-style symbol algorithm

Quadratic reciprocity can be organised algorithmically. Repeatedly remove powers of 2, reduce the numerator modulo the denominator, swap numerator and denominator, and update the sign according to the supplementary laws and reciprocity rule.

The pattern resembles Euclid’s algorithm: the pair of integers shrinks while a carefully controlled invariant—the symbol value—survives through sign changes.

9. The Jacobi symbol

For an odd positive integer n with prime factorisation n=∏p_i^{e_i}, define

(a/n)=∏(a/p_i)^{e_i}.

This is the Jacobi symbol. It obeys many of the same algebraic rules as the Legendre symbol and can be computed without factoring n by a reciprocity algorithm.

But there is a crucial difference: Jacobi symbol 1 does not guarantee that a is a square modulo composite n.

Example: Jacobi 1 without a square root

Take a=2,n=15. Since (2/3)=−1 and (2/5)=−1, the Jacobi symbol is (+1). Yet x²≡2 (mod 15) has no solution. The two negative local symbols multiply to +1 even though neither prime component admits a root.

Legendre 1 is an existence statement. Jacobi 1 is only a compressed parity statement across prime factors.

10. Square roots modulo primes with p≡3 mod 4

When p≡3 (mod 4), modular square roots have an especially simple formula. If a is a quadratic residue, then

x≡a^((p+1)/4) (mod p)

is a square root. Squaring gives a^((p+1)/2)=a·a^((p−1)/2)≡a by Euler’s criterion.

Example: √5 mod 11

Because 11≡3 mod 4, compute 5^3=125≡4. Then 4²=16≡5, so the roots are 4 and −4≡7.

11. Why a general algorithm is needed

For primes p≡1 mod 4, the simple exponent formula above no longer applies. The multiplicative group has a larger power of 2 in its order p−1, and the root-finding problem must explicitly handle that 2-adic structure.

Tonelli–Shanks does exactly this.

12. Tonelli–Shanks setup

Let p be an odd prime and suppose (a/p)=1. Write

p−1=q·2^s with q odd.

Choose a quadratic nonresidue z modulo p. The algorithm maintains quantities whose powers progressively eliminate the unwanted 2-power component until the correction term becomes 1.

c = z^q mod p
t = a^q mod p
r = a^((q+1)/2) mod p
m = s

while t ≠ 1:
    find least i with 0 < i < m and t^(2^i)=1
    b = c^(2^(m−i−1)) mod p
    r = r·b mod p
    t = t·b² mod p
    c = b² mod p
    m = i

return r

The returned r satisfies r²≡a (mod p). The second root is p−r.

13. Worked Tonelli–Shanks example: √5 mod 41

First verify that 5 is a quadratic residue modulo 41. Euler’s criterion gives 5^20≡1.

Factor p−1=40=5·2³, so q=5,s=3. Choose z=3; 3 is a quadratic nonresidue modulo 41. Initialise:

c = 3^5 mod 41 = 38
t = 5^5 mod 41 = 9
r = 5^3 mod 41 = 2
m = 3.

Now t=9. We find t²=81≡−1 and t⁴≡1, so the least i is 2. Then b=c^(2^(3−2−1))=c=38.

r ← 2·38 ≡ 35
t ← 9·38² ≡ 40
c ← 38² ≡ 9
m ← 2.

Now t=−1. The least i with t^(2^i)=1 is i=1. Set b=c=9:

r ← 35·9 ≡ 28
t ← 40·9² ≡ 1.

The loop stops. One root is 28, and the other is 41−28=13. Check: 13²=169≡5 and 28²=784≡5 (mod 41).

14. Verification is cheap

Whatever root algorithm is used, verification requires one modular square. If r is claimed to satisfy r²≡a (mod p), compute r² mod p and compare with a mod p. This is much cheaper than rediscovering the root independently.

15. Roots modulo a composite modulus

When n is composite and its prime-power factorisation is known, square roots can often be found locally modulo each prime power and recombined with the Chinese Remainder Theorem.

For a squarefree n=pq with odd distinct primes, a residue that is a square modulo both p and q usually has four roots modulo pq because each prime contributes two sign choices. CRT turns the sign pairs into four global residue classes.

This is another example of decomposition: solve smaller local problems, then reconstruct the global answer.

16. Hensel lifting idea

If a root is known modulo p and a derivative condition is nonzero modulo p, Hensel-type lifting can extend the root to p²,p³ and higher prime powers. For f(x)=x²−a, the derivative is 2x.

The general philosophy is Newton-like: correct an approximate modular root one power of p at a time while preserving the congruence to increasing precision.

17. Symbol computation versus root computation

It is important to separate the jobs.

Legendre/Jacobi symbol: classify or compress residue behaviour.
Euler criterion: test the Legendre symbol through modular exponentiation.
Quadratic reciprocity: transform symbol calculations efficiently.
Tonelli–Shanks: construct a square root after existence is known.
CRT: recombine local roots across coprime moduli.

A yes/no oracle is not automatically a constructor. Algorithmic number theory often distinguishes decision problems from search problems even when they are mathematically related.

18. Common mistakes

Assuming every residue has a square root. Only half of the nonzero residues modulo an odd prime are squares.
Treating Jacobi symbol 1 as proof of a root modulo composite n. It is not sufficient.
Forgetting the zero case. If p|a, the Legendre symbol is 0.
Using the p≡3 mod 4 shortcut for a general prime. Check the congruence class first.
Running Tonelli–Shanks before checking existence. First verify (a/p)=1.
Returning one root and forgetting the other. For nonzero a modulo odd prime p, roots occur as ±r.

19. Practice set

List the nonzero quadratic residues modulo 17.
Determine whether 6 is a quadratic residue modulo 13.
Evaluate (−1/19).
Evaluate (2/23).
Use Euler’s criterion to evaluate (5/29).
Find the square roots of 5 modulo 29.
Evaluate (19/43) using quadratic reciprocity.
Explain why Jacobi (2/15)=1 does not imply a square root modulo 15.
Find √5 modulo 11 using the p≡3 mod 4 shortcut.
Verify that 13 and 28 are the two roots of 5 modulo 41.
Explain why nonzero roots modulo an odd prime occur in pairs.
Describe how CRT can turn two pairs of local roots into four roots modulo pq.

20. Answers and checks

1. Squares of 1 through 8 give {1,2,4,8,9,13,15,16} modulo 17.

2. 6^6≡12≡−1 (mod 13), so 6 is a nonresidue.

3. Since 19≡3 mod 4, (−1/19)=−1.

4. Since 23≡7≡−1 mod 8, (2/23)=1.

5. 5^14≡1 (mod 29), so (5/29)=1.

6. The roots are 11 and 18 because 11²=121≡5 and 18≡−11.

7. Both primes are 3 mod 4, so (19/43)=−(43/19)=−(5/19)=−1.

8. The Jacobi symbol multiplies local signs: (2/3)(2/5)=(−1)(−1)=1, but neither local congruence has a root.

9. 5^3≡4 (mod 11), so the roots are 4 and 7.

10. 13²=169≡5 and 28²=784≡5 modulo 41.

11. If r²≡a, then (−r)²=r²≡a. For nonzero a modulo odd prime p, r and −r are distinct.

12. Choose either sign modulo p and either sign modulo q. The four sign pairs reconstruct four distinct residues modulo pq by CRT.

21. Continue the Computational Number Theory series

Return to the Singapore Mathematics Hub for the wider BTT Mathematics library.

Small Group Tutorials

Computational Number Theory 5: Quadratic Residues, Legendre & Jacobi Symbols and Tonelli–Shanks