Quadratic residues and the Legendre symbol
A linear congruence modulo a prime is settled by one inverse. Which numbers have a square root modulo a prime, and how can we tell without listing every square?
Where you are 5 in Quadratic residues and beyond
Why this exists
A linear congruence ax \equiv b \pmod{p} with p prime and p \nmid a has exactly one solution modulo p, found with an inverse (Modular inverses and linear congruences). The next case is quadratic. Let p be an odd prime and p \nmid a. Multiplying ax^2 + bx + c \equiv 0 \pmod{p} by the invertible 4a and completing the square gives the equivalent congruence
as in the The quadratic formula. Since 2a is invertible, each square root y of b^2 - 4ac gives exactly one x, from 2ax + b \equiv y. So every quadratic congruence modulo an odd prime comes down to one question: which integers are perfect squares modulo p? This lesson gives a test for any prime and any a, Euler’s criterion, and rules that settle -1 and 2 for every prime.
Definition
Let p be an odd prime and a an integer with p \nmid a. Then a is a quadratic residue modulo p if the congruence x^2 \equiv a \pmod{p} has a solution, and a quadratic nonresidue modulo p if it has none. A multiple of p is called neither.
The Legendre symbol records the answer:
It is read “a over p” but is not a fraction. For a modulus n that is not prime, an integer a with \gcd(a, n) = 1 is a quadratic residue modulo n when x^2 \equiv a \pmod{n} is solvable; Boundaries says what changes there.
Intuition
Squaring 1, 2, \dots, 12 modulo 13 gives
The list reads the same backward, because (13 - x)^2 = 169 - 26x + x^2 \equiv x^2. So only six values occur, 1, 3, 4, 9, 10, 12, each twice: half of the nonzero remainders are squares, and each square has the two square roots x and -x.
A primitive root shows which half (Primitive roots). The number 2 is a primitive root modulo 13, so every nonzero remainder is 2^k for exactly one k with 0 \le k \le 11, and squaring 2^k gives the even power 2^{2k}. Place the remainders around a circle in the order 2^0, 2^1, \dots, 2^{11}: the squares are every other point.
Two steps around the circle is multiplication by 2^2 = 4, so the squares form one closed hexagon and the nonsquares the other. Multiplying by a square moves an even number of steps and keeps a point on its hexagon; multiplying by a nonsquare moves an odd number and switches hexagons. That is the multiplication rule of Theorem 4.
Results
Throughout, p is an odd prime and \displaystyle m = \frac{p-1}{2}.
Theorem 1 (two roots or none). Let p \nmid a. If x^2 \equiv a \pmod{p} has a solution r, then it has exactly two solutions modulo p, namely r and -r.
Theorem 2 (half are squares). Exactly m of the integers 1, 2, \dots, p - 1 are quadratic residues modulo p: the remainders of 1^2, 2^2, \dots, m^2, which are pairwise incongruent. If g is a primitive root modulo p and p \nmid a, then a is a quadratic residue exactly when \operatorname{ind}_g(a) is even; that is, \displaystyle \left(\frac{a}{p}\right) = (-1)^{\operatorname{ind}_g(a)}.
Theorem 3 (Euler’s criterion). For every integer a, \displaystyle \left(\frac{a}{p}\right) \equiv a^{m} \pmod{p}.
Theorem 4 (rules for the symbol). For all integers a and b: (a) if a \equiv b \pmod{p}, then \displaystyle \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right); (b) \displaystyle \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right); (c) if p \nmid b, then \displaystyle \left(\frac{ab^2}{p}\right) = \left(\frac{a}{p}\right); (d) \displaystyle \sum_{a=1}^{p-1} \left(\frac{a}{p}\right) = 0. By (b), a product of two residues is a residue, a residue times a nonresidue is a nonresidue, and a product of two nonresidues is a residue.
Theorem 5 (the symbol of -1). \displaystyle \left(\frac{-1}{p}\right) = (-1)^{m}. So -1 is a quadratic residue modulo p if p \equiv 1 \pmod{4} and a nonresidue if p \equiv 3 \pmod{4}.
Corollary 6. There are infinitely many primes p with p \equiv 1 \pmod{4}.
Theorem 7 (Gauss’s lemma). Let p \nmid a, and let \mu be the number of the integers a, 2a, \dots, ma whose least positive residue modulo p is greater than \displaystyle \frac{p}{2}. Then \displaystyle \left(\frac{a}{p}\right) = (-1)^{\mu}.
Theorem 8 (the symbol of 2). \displaystyle \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}. So 2 is a quadratic residue modulo p if p \equiv \pm 1 \pmod{8} and a nonresidue if p \equiv \pm 3 \pmod{8}.
There are infinitely many primes proves that there are infinitely many primes 4k + 3; Corollary 6 is the other half.
Why it is true
Two facts are used throughout. Euclid’s lemma (Bezout's identity and the extended Euclidean algorithm): if a prime divides a product, it divides a factor. And since p \ge 3, the numbers 1, 0 and -1 are pairwise incongruent modulo p, so two values in \{-1, 0, 1\} that are congruent modulo p are equal.
Proof of Theorem 1. (-r)^2 = r^2 \equiv a, so -r is a solution. As p \nmid a \equiv r^2, we have p \nmid r; if r \equiv -r, then p \mid 2r, which Euclid’s lemma forbids for odd p. If s is any solution, (s - r)(s + r) = s^2 - r^2 \equiv a - a = 0, so p divides s - r or s + r: s \equiv r or s \equiv -r. \square
Proof of Theorem 2. Let 1 \le i, j \le m with i^2 \equiv j^2. By Theorem 1 (with a = j^2), i \equiv \pm j. But 2 \le i + j \le p - 1, so i \not\equiv -j; hence i \equiv j, and i = j. So 1^2, \dots, m^2 give m distinct residues. Every x in 1, \dots, p - 1 has x or p - x in 1, \dots, m, and (p - x)^2 \equiv x^2, so there are no others.
By Corollary 3 of Primitive roots, g^0, g^1, \dots, g^{p-2} are congruent, in some order, to 1, \dots, p - 1. The m even powers g^{2k} = (g^k)^2 with 0 \le k < m are residues and pairwise incongruent, so they are all m residues, and the m odd powers are the nonresidues. \square
Proof of Theorem 3. If p \mid a, both sides are 0. Otherwise let k = \operatorname{ind}_g(a) for a primitive root g, so a \equiv g^k. By Theorem 8 of Primitive roots, g^{m} \equiv -1. Hence \displaystyle a^{m} \equiv (g^{m})^k \equiv (-1)^k = \left(\frac{a}{p}\right) by Theorem 2. \square
Proof of Theorem 4. (a) The congruences x^2 \equiv a and x^2 \equiv b have the same solutions, and p \mid a exactly when p \mid b. (b) By Theorem 3, \displaystyle \left(\frac{ab}{p}\right) \equiv (ab)^m = a^m b^m \equiv \left(\frac{a}{p}\right)\left(\frac{b}{p}\right); both sides lie in \{-1, 0, 1\}, so they are equal. (c) By (b), \displaystyle \left(\frac{ab^2}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)^2, and \displaystyle \left(\frac{b}{p}\right) = \pm 1. (d) By Theorem 2 the sum has m terms 1 and m terms -1. \square
Proof of Theorem 5. Theorem 3 with a = -1 gives \displaystyle \left(\frac{-1}{p}\right) \equiv (-1)^m, and both sides are \pm 1. Finally \displaystyle m = \frac{p-1}{2} is even exactly when 4 \mid p - 1. \square
Proof of Corollary 6. Suppose q_1, \dots, q_k are all the primes \equiv 1 \pmod{4} (5 is one, so k \ge 1). Let N = (2q_1 \cdots q_k)^2 + 1. Then N > 1 is odd, so it has an odd prime factor p, and (2q_1 \cdots q_k)^2 \equiv -1 \pmod{p}. So \displaystyle \left(\frac{-1}{p}\right) = 1 and p \equiv 1 \pmod{4} by Theorem 5; thus p = q_i for some i. But then p divides both N and (2q_1 \cdots q_k)^2, hence their difference 1, which is impossible. \square
Proof of Theorem 7. For 1 \le j \le m let r_j be the least positive residue of ja. Since p \nmid j and p \nmid a, Euclid’s lemma gives p \nmid ja, so 1 \le r_j \le p - 1, and \displaystyle r_j \ne \frac{p}{2} as p is odd. Let s_1, \dots, s_{\mu} be the r_j greater than \displaystyle \frac{p}{2} and t_1, \dots, t_{\nu} the others, so \mu + \nu = m. The m numbers
all lie in 1, \dots, m. They are distinct. If r_i = r_j, then ia \equiv ja, so i \equiv j on canceling a (Modular inverses and linear congruences), and i = j. If r_i = p - r_j, then ia \equiv -ja, so p \mid (i + j)a and p \mid i + j, impossible as 2 \le i + j \le p - 1. So these are 1, 2, \dots, m in some order. Multiplying them, and using r_1 \cdots r_m \equiv a \cdot 2a \cdots ma,
As p \nmid m!, canceling gives a^m \equiv (-1)^{\mu}, and Theorem 3 gives \displaystyle \left(\frac{a}{p}\right) \equiv (-1)^{\mu}; both sides are \pm 1. \square
Proof of Theorem 8. Take a = 2. The numbers 2, 4, \dots, 2m = p - 1 are their own least positive residues, and \displaystyle 2j > \frac{p}{2} exactly when \displaystyle j > \frac{p}{4}. So \mu counts the integers j with \displaystyle \frac{p}{4} < j \le m, and \mu = m - \lfloor p/4 \rfloor. Write p = 8k + r:
| p | m | \lfloor p/4 \rfloor | \mu | \displaystyle \frac{p^2 - 1}{8} |
|---|---|---|---|---|
| 8k + 1 | 4k | 2k | 2k | 8k^2 + 2k |
| 8k + 3 | 4k + 1 | 2k | 2k + 1 | 8k^2 + 6k + 1 |
| 8k + 5 | 4k + 2 | 2k + 1 | 2k + 1 | 8k^2 + 10k + 3 |
| 8k + 7 | 4k + 3 | 2k + 1 | 2k + 2 | 8k^2 + 14k + 6 |
In each row \mu and \displaystyle \frac{p^2-1}{8} have the same parity, so Theorem 7 gives the formula; both are even exactly when p \equiv 1 or 7 \equiv -1 \pmod{8}. \square
Worked examples
Squares modulo 23
List the quadratic residues modulo 23, and solve x^2 \equiv 13 \pmod{23}.
SolutionBy Theorem 2 it is enough to square 1, \dots, 11: the remainders are 1, 4, 9, 16, 25 \equiv 2, 36 \equiv 13, 49 \equiv 3, 64 \equiv 18, 81 \equiv 12, 100 \equiv 8 and 121 \equiv 6. So the quadratic residues modulo 23 are
eleven of them. Since 6^2 \equiv 13, Theorem 1 gives the solutions x \equiv \pm 6, that is, x \equiv 6, 17 \pmod{23}. Check: 17^2 = 289 = 12 \cdot 23 + 13.
Euler’s criterion by repeated squaring
Decide whether 6 is a quadratic residue modulo 53, and if it is, find its square roots.
SolutionHere m = 26 = 16 + 8 + 2. Squaring repeatedly (Powers modulo n): 6^2 = 36, 6^4 = 1296 = 24 \cdot 53 + 24 \equiv 24, 6^8 \equiv 576 = 10 \cdot 53 + 46 \equiv -7 and 6^{16} \equiv 49 \equiv -4. So
and \displaystyle \left(\frac{6}{53}\right) = 1 by Theorem 3. Euler’s criterion does not produce the root. To find it, run through the integers \equiv 6 \pmod{53} until a perfect square appears: 6, 59, 112, 165, 218, 271, 324 = 18^2. By Theorem 1 the square roots are x \equiv 18, 35 \pmod{53}.
Gauss’s lemma for 7 modulo 17
Evaluate \displaystyle \left(\frac{7}{17}\right) with Gauss’s lemma.
SolutionHere m = 8. The multiples 7, 14, 21, 28, 35, 42, 49, 56 have least positive residues 7, 14, 4, 11, 1, 8, 15, 5 modulo 17. Of these, 14, 11 and 15 exceed \displaystyle \frac{17}{2}, so \mu = 3 and \displaystyle \left(\frac{7}{17}\right) = (-1)^3 = -1.
As in the proof of Theorem 7, the large ones reflect to 17 - 14 = 3, 17 - 11 = 6 and 17 - 15 = 2, and with 7, 4, 1, 8, 5 they give each of 1, \dots, 8 once. Check: squaring 1, \dots, 8 modulo 17 gives 1, 4, 9, 16, 8, 2, 15, 13, and 7 is not among them.
Which primes divide a value of a quadratic
Find every prime p that divides n^2 + 4n + 6 for some integer n, and find all such n modulo 11.
SolutionModulo 2, n^2 + 4n + 6 \equiv n^2, so 2 divides it exactly when n is even. Let p be odd. Since n^2 + 4n + 6 = (n + 2)^2 + 2, the prime p divides it exactly when (n + 2)^2 \equiv -2 \pmod{p}, which has a solution exactly when \displaystyle \left(\frac{-2}{p}\right) = 1. By Theorem 4(b) this symbol is \displaystyle \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right), and Theorems 5 and 8 give it from p \bmod 8:
| p \bmod 8 | 1 | 3 | 5 | 7 |
|---|---|---|---|---|
| \displaystyle \left(\frac{-1}{p}\right) | 1 | -1 | 1 | -1 |
| \displaystyle \left(\frac{2}{p}\right) | 1 | -1 | -1 | 1 |
| \displaystyle \left(\frac{-2}{p}\right) | 1 | 1 | -1 | -1 |
So the primes are 2 and the odd primes p \equiv 1 or 3 \pmod{8}: 2, 3, 11, 17, 19, 41, 43, \dots; no value is ever divisible by 5, 7 or 13. For p = 11, -2 \equiv 9 = 3^2, so n + 2 \equiv \pm 3, giving n \equiv 1 or n \equiv -5 \equiv 6 \pmod{11}. Check: 1 + 4 + 6 = 11 and 36 + 24 + 6 = 66 = 6 \cdot 11.
A quiz bowl bonus
At quiz bowl practice, Layla reads Omar a bonus question: find an x with x^2 \equiv 17 \pmod{43}. Show that if p \equiv 3 \pmod{4} and \displaystyle \left(\frac{a}{p}\right) = 1, then the square roots of a modulo p are x \equiv \pm a^{(p+1)/4}, and use this to answer the bonus.
SolutionAs p \equiv 3 \pmod 4, \displaystyle \frac{p+1}{4} is an integer. Let x = a^{(p+1)/4}. Then x^2 = a^{(p+1)/2} = a \cdot a^{(p-1)/2} \equiv a \cdot 1 = a by Theorem 3, and by Theorem 1 the square roots are \pm x.
For p = 43, \displaystyle \frac{p+1}{4} = 11 and m = 21. Squaring: 17^2 = 289 = 6 \cdot 43 + 31 \equiv -12, 17^4 \equiv 144 \equiv 15 and 17^8 \equiv 225 \equiv 10. So 17^{11} = 17^8 \cdot 17^2 \cdot 17 \equiv 10(-12)(17), and as -120 \equiv 9 and 9 \cdot 17 = 153 = 3 \cdot 43 + 24, 17^{11} \equiv 24. Omar confirms that 17 is a residue:
The answers are x \equiv 24 and x \equiv -24 \equiv 19 \pmod{43}. Check: 24^2 = 576 = 13 \cdot 43 + 17.
A proof: an explicit square root of 2
Let p \equiv 1 \pmod{8}. Prove that 2 is a quadratic residue modulo p without Gauss’s lemma, by writing down a square root of 2.
SolutionProof. Let g be a primitive root modulo p (Theorem 7 of Primitive roots) and x = g^{(p-1)/8}. By Theorem 2 of that lesson, \displaystyle \operatorname{ord}_p(x) = \frac{p-1}{\gcd(p - 1, (p-1)/8)} = 8. Then y = x^4 has y^2 \equiv 1, so y \equiv \pm 1 by Theorem 1 above, and y \not\equiv 1 as 4 < 8. So x^4 \equiv -1. Let x' be an inverse of x modulo p. Since x x' \equiv 1, we have x'^2 x^4 \equiv x^2, and
So x + x' is a square root of 2. \square
Any x with x^4 \equiv -1 serves. For p = 41, 3^4 = 81 \equiv -1, the inverse of 3 is 14 (as 3 \cdot 14 = 42), and 3 + 14 = 17 has 17^2 = 289 = 7 \cdot 41 + 2. So the square roots of 2 modulo 41 are 17 and 24.
Boundaries
- The prime 2. Every integer is \equiv 0 or 1 = 1^2 \pmod 2, and r \equiv -r always, so there is no half and no pair of roots. The symbol is defined for odd primes only.
- Composite moduli. Theorem 2’s count fails: modulo 15 the eight units square to only 1 and 4. Euler’s criterion fails with it: \displaystyle \frac{\varphi(15)}{2} = 4 and 2^4 \equiv 1 \pmod{15}, yet 2 is not a square modulo 15. By the The Chinese remainder theorem, an a coprime to n is a square modulo n exactly when it is one modulo each prime power exactly dividing n.
- A composite denominator. The Jacobi symbol of Quadratic reciprocity writes \displaystyle \left(\frac{a}{n}\right) for odd n as a product of Legendre symbols. For n = 15 it gives \displaystyle \left(\frac{2}{3}\right)\left(\frac{2}{5}\right) = 1, although 2 is not a square modulo 15: a value -1 proves a nonresidue, a value 1 proves nothing.
- A test, not a construction. Theorem 3 decides whether a root exists but does not find one. For p \equiv 3 \pmod 4 Example 5 gives it; for p \equiv 1 \pmod 4 more is needed (the Tonelli-Shanks algorithm, not covered here).
- Odd primes on top. Theorems 5 and 8 settle -1 and 2 for every p at once; for an odd prime q, the matching rule for \displaystyle \left(\frac{q}{p}\right) is quadratic reciprocity.
Where this goes next
Quadratic reciprocity ties \displaystyle \left(\frac{p}{q}\right) to \displaystyle \left(\frac{q}{p}\right) for distinct odd primes, and with Theorems 4, 5 and 8 it evaluates any Legendre symbol with no large powers; one proof of it starts from Gauss’s lemma. Sums of two squares starts from Theorem 5: when p \equiv 1 \pmod 4 some x has p \mid x^2 + 1, and that x leads to p = a^2 + b^2. In Finite fields, the same count shows that half of the nonzero elements of a finite field of odd order are squares.
Exercises
Residues and symbols
- List the quadratic residues modulo 29.
- Solve x^2 \equiv 5 \pmod{29}.
- Use Euler’s criterion to find \displaystyle \left(\frac{3}{37}\right) and \displaystyle \left(\frac{2}{37}\right).
- Use Gauss’s lemma to find \displaystyle \left(\frac{5}{23}\right), and compare with Example 1.
- For each of p = 101, 103 and 107, decide which of -1, 2 and -2 are quadratic residues modulo p.
- Evaluate \displaystyle \left(\frac{-8}{43}\right) and \displaystyle \left(\frac{50}{43}\right) using Theorems 4, 5 and 8 only.
Solving quadratic congruences
- Solve x^2 + 3x + 5 \equiv 0 modulo 13 and modulo 23, or show there is no solution.
- Given that 2 is a primitive root modulo 29 and modulo 37, find the square roots of -1 modulo each.
- Use the method of Example 5 to find the square roots of 2 modulo 47.
- For n = 9 and n = 15, list the integers a with 1 \le a < n and \gcd(a, n) = 1 for which x^2 \equiv a \pmod{n} is solvable.
- Find every prime p < 50 that divides n^2 - 2 for some integer n.
Proofs
Throughout, p is an odd prime.
- Prove that a primitive root modulo p is a quadratic nonresidue modulo p.
- Let p = 2^k + 1 with k \ge 1. Prove that every quadratic nonresidue modulo p is a primitive root modulo p, and deduce that 3 is a primitive root modulo 17.
- Let p \nmid a. Prove that if p \equiv 1 \pmod 4, then a and -a are both residues or both nonresidues, and that if p \equiv 3 \pmod 4, exactly one of them is a residue.
- Prove that for every integer a the congruence x^2 \equiv a \pmod{p} has exactly \displaystyle 1 + \left(\frac{a}{p}\right) solutions modulo p.
- Prove that the product of the quadratic residues among 1, \dots, p - 1 is \equiv (-1)^{(p+1)/2} \pmod{p}.
- Let p \equiv 1 \pmod 4. Using Wilson’s theorem, (p - 1)! \equiv -1 \pmod{p} (an exercise in Modular inverses and linear congruences), prove that \displaystyle x = \left(\frac{p-1}{2}\right)! satisfies x^2 \equiv -1 \pmod{p}.
- Prove that there are infinitely many primes q \equiv 7 \pmod{8}. (Consider (q_1 \cdots q_k)^2 - 2.)
Answers
- The residues are 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28. Squaring 1, \dots, 14 gives 1, 4, 9, 16, 25, 36 \equiv 7, 49 \equiv 20, 64 \equiv 6, 81 \equiv 23, 100 \equiv 13, 121 \equiv 5, 144 \equiv 28, 169 \equiv 24, 196 \equiv 22: fourteen, as Theorem 2 says.
- x \equiv 11, 18 \pmod{29}. From Exercise 1, 11^2 = 121 = 4 \cdot 29 + 5, and the other root is -11 \equiv 18 by Theorem 1.
- \displaystyle \left(\frac{3}{37}\right) = 1 and \displaystyle \left(\frac{2}{37}\right) = -1. Here m = 18. Powers of 3: 3^3 = 27 \equiv -10, 3^6 \equiv 100 \equiv -11, 3^9 \equiv 110 \equiv -1, so 3^{18} \equiv 1. Powers of 2: 2^5 = 32 \equiv -5, 2^{10} \equiv 25, 2^{15} \equiv -125 \equiv 23, 2^{18} \equiv 184 \equiv -1. The second agrees with Theorem 8, as 37 \equiv 5 \pmod 8.
- \displaystyle \left(\frac{5}{23}\right) = -1. With m = 11, the residues of 5j are 5, 10, 15, 20, 2, 7, 12, 17, 22, 4, 9; those above \displaystyle \frac{23}{2} are 15, 20, 12, 17, 22, so \mu = 5. Example 1 does not list 5 among the residues.
- 101 \equiv 5 \pmod 8: only -1 is a residue. 103 \equiv 7 \pmod 8: only 2 is a residue. 107 \equiv 3 \pmod 8: only -2 is a residue. Read off from the table in Example 4.
- \displaystyle \left(\frac{-8}{43}\right) = 1 and \displaystyle \left(\frac{50}{43}\right) = -1. As 43 \equiv 3 \pmod 8, \displaystyle \left(\frac{-1}{43}\right) = \left(\frac{2}{43}\right) = -1. Since -8 = (-2) \cdot 2^2, Theorem 4(b) and (c) give \displaystyle \left(\frac{-1}{43}\right)\left(\frac{2}{43}\right) = 1; since 50 = 2 \cdot 5^2, \displaystyle \left(\frac{50}{43}\right) = \left(\frac{2}{43}\right) = -1.
- No solution modulo 13; x \equiv 3, 17 \pmod{23}. Multiplying by 4, which is invertible modulo both, gives (2x + 3)^2 \equiv 9 - 20 = -11. Modulo 13, -11 \equiv 2, and \displaystyle \left(\frac{2}{13}\right) = -1 as 13 \equiv 5 \pmod 8. Modulo 23, -11 \equiv 12 \equiv 9^2 (Example 1), so 2x + 3 \equiv \pm 9: 2x \equiv 6 gives x \equiv 3, and 2x \equiv -12 gives x \equiv -6 \equiv 17. Check: 9 + 9 + 5 = 23 and 289 + 51 + 5 = 345 = 15 \cdot 23.
- Modulo 29: x \equiv 12, 17. Modulo 37: x \equiv 6, 31. With x = g^{(p-1)/4}, x^2 = g^{(p-1)/2} \equiv -1 (Theorem 8 of Primitive roots). Modulo 29, 2^7 = 128 = 4 \cdot 29 + 12, and 12^2 = 144 = 5 \cdot 29 - 1. Modulo 37, 2^9 = 512 = 14 \cdot 37 - 6, so the roots are \pm 6, and 6^2 = 36 \equiv -1.
- x \equiv 7, 40 \pmod{47}. As 47 \equiv 7 \pmod 8, \displaystyle \left(\frac{2}{47}\right) = 1 by Theorem 8, and \displaystyle \frac{47+1}{4} = 12: 2^6 = 64 \equiv 17 and 2^{12} \equiv 289 = 6 \cdot 47 + 7. Check: 7^2 = 49 \equiv 2.
- Modulo 9: 1, 4, 7, half of the six units (1^2 = 1, 2^2 = 4, 4^2 = 16 \equiv 7, and 9 - x squares like x). Modulo 15: 1 and 4 only, a quarter of the eight units: 1, 4, 11, 14 square to 1, and 2, 7, 8, 13 square to 4.
- 2, 7, 17, 23, 31, 41, 47. The prime 2 divides 0^2 - 2. An odd prime p divides some n^2 - 2 exactly when \displaystyle \left(\frac{2}{p}\right) = 1, that is, p \equiv \pm 1 \pmod 8 by Theorem 8. For instance 3^2 - 2 = 7.
- Proof. Let g be a primitive root modulo p. Its index to the base g is 1, which is odd, so \displaystyle \left(\frac{g}{p}\right) = -1 by Theorem 2. \square
- Proof. Here \varphi(p) = p - 1 = 2^k, whose only prime factor is 2. If a is a nonresidue, a^{(p-1)/2} \equiv -1 \not\equiv 1 by Theorem 3, so a is a primitive root by Theorem 4 of Primitive roots. For 17 = 2^4 + 1, the squares modulo 17 are 1, 2, 4, 8, 9, 13, 15, 16 (Example 3), so 3 is a nonresidue and hence a primitive root. \square
- Proof. By Theorem 4(b), \displaystyle \left(\frac{-a}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{a}{p}\right). If p \equiv 1 \pmod 4, then \displaystyle \left(\frac{-1}{p}\right) = 1 by Theorem 5 and the two symbols are equal. If p \equiv 3 \pmod 4, then \displaystyle \left(\frac{-1}{p}\right) = -1 and they are opposite, so exactly one is 1. \square
- Proof. If p \mid a, then x^2 \equiv 0 forces p \mid x by Euclid’s lemma: one solution, and 1 + 0 = 1. If \displaystyle \left(\frac{a}{p}\right) = 1, there are two solutions by Theorem 1, and 1 + 1 = 2. If \displaystyle \left(\frac{a}{p}\right) = -1, there are none, and 1 - 1 = 0. \square
- Proof. Let g be a primitive root and \displaystyle m = \frac{p-1}{2}. By Theorem 2 the residues are congruent to g^0, g^2, \dots, g^{2(m-1)}, so their product is congruent to g^{2(0 + 1 + \dots + (m-1))} = g^{m(m-1)}, which is (g^m)^{m-1} \equiv (-1)^{m-1}, using g^m \equiv -1 (Theorem 8 of Primitive roots). Finally \displaystyle m - 1 = \frac{p+1}{2} - 2 has the parity of \displaystyle \frac{p+1}{2}. \square
- Proof. Let \displaystyle m = \frac{p-1}{2}. Pair each j with 1 \le j \le m with p - j \equiv -j:
By Wilson’s theorem the left side is \equiv -1, and m is even as p \equiv 1 \pmod 4, so (m!)^2 \equiv -1. \square 18. Proof. Suppose q_1, \dots, q_k are all the primes \equiv 7 \pmod 8 (7 is one). Let N = (q_1 \cdots q_k)^2 - 2. The product is odd, and an odd square is \equiv 1 \pmod 8, since (2t + 1)^2 = 4t(t + 1) + 1 with t(t + 1) even. So N \equiv 7 \pmod 8; in particular N is odd, and N \ge 49 - 2 > 1. Every prime factor q of N is odd and has (q_1 \cdots q_k)^2 \equiv 2 \pmod q, so \displaystyle \left(\frac{2}{q}\right) = 1 and q \equiv \pm 1 \pmod 8 by Theorem 8. If every prime factor were \equiv 1 \pmod 8, so would their product N be. So some prime factor is \equiv 7 \pmod 8, hence equals some q_i, and then it divides N and (q_1 \cdots q_k)^2, hence 2, which is impossible. \square