Quadratic reciprocity
Euler’s criterion decides whether q is a square modulo p, but only through a large power. Is there a rule that answers from p and q alone, the way p mod 8 settles whether 2 is a square?
Where you are 5 in Quadratic residues and beyond
Why this exists
Quadratic residues and the Legendre symbol gives two ways to evaluate a Legendre symbol \displaystyle \left(\frac{a}{p}\right). Euler’s criterion, \displaystyle \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}, works for every a but costs a large power. The rules for -1 and 2 are far better: whether 2 is a square modulo p depends only on p \bmod 8, with no arithmetic modulo p at all. Since the symbol is multiplicative, a factored top a = \pm 2^e q_1 \cdots q_k reduces every symbol to symbols \displaystyle \left(\frac{q}{p}\right) with q an odd prime. What is missing is a rule for those.
Quadratic reciprocity is that rule. “Is q a square modulo p?” and “is p a square modulo q?” have the same answer, unless p and q both leave remainder 3 on division by 4, when the answers are opposite. So a symbol can be flipped and reduced until it is small. The pattern was found by experiment in the eighteenth century and first proved by Gauss in 1796.
Definition
The law of quadratic reciprocity. Let p and q be distinct odd primes. Then
The exponent is odd exactly when \displaystyle \frac{p-1}{2} and \displaystyle \frac{q-1}{2} are both odd, that is, when p \equiv q \equiv 3 \pmod 4. Both symbols are \pm 1, so the law says: \displaystyle \left(\frac{p}{q}\right) = \left(\frac{q}{p}\right) if p or q is \equiv 1 \pmod 4, and \displaystyle \left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right) if both are \equiv 3 \pmod 4. Together with \displaystyle \left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} and \displaystyle \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} (Theorems 5 and 8 of Quadratic residues and the Legendre symbol), often called the supplementary laws, it evaluates every Legendre symbol.
The Jacobi symbol. Let n be an odd positive integer, written as a product of primes n = p_1 p_2 \cdots p_k (repeats allowed). For an integer a the Jacobi symbol is
each factor a Legendre symbol, and \displaystyle \left(\frac{a}{1}\right) = 1. For prime n it is the Legendre symbol. For composite n it does not say whether a is a square modulo n (see Boundaries); it is a tool for computing Legendre symbols.
Intuition
The table gives \displaystyle \left(\frac{p}{q}\right) for the first five odd primes, read off from the squares modulo 3 (1), 5 (1, 4), 7 (1, 2, 4), 11 (1, 3, 4, 5, 9) and 13 (1, 3, 4, 9, 10, 12).
| \displaystyle \left(\frac{p}{q}\right) | q = 3 | q = 5 | q = 7 | q = 11 | q = 13 |
|---|---|---|---|---|---|
| p = 3 | -1 | -1 | 1 | 1 | |
| p = 5 | -1 | -1 | 1 | -1 | |
| p = 7 | 1 | -1 | -1 | -1 | |
| p = 11 | -1 | 1 | 1 | -1 | |
| p = 13 | 1 | -1 | -1 | -1 |
The table is symmetric across its diagonal except for the three pairs drawn from 3, 7, 11, the primes \equiv 3 \pmod 4, where the entries are opposite: \displaystyle \left(\frac{3}{7}\right) = -1 but \displaystyle \left(\frac{7}{3}\right) = 1.
The proof below turns each sign into a count. Gauss’s lemma, sharpened, writes \displaystyle \left(\frac{q}{p}\right) as -1 to the number of lattice points below the line py = qx in a rectangle, and \displaystyle \left(\frac{p}{q}\right) as -1 to the number above it. Together they count the whole rectangle, which has \displaystyle \frac{p-1}{2} \cdot \frac{q-1}{2} points.
For p = 11 and q = 7 the rectangle holds 5 \cdot 3 = 15 points, 7 below the line and 8 above, so \displaystyle \left(\frac{7}{11}\right)\left(\frac{11}{7}\right) = (-1)^{15} = -1. Indeed \displaystyle \left(\frac{11}{7}\right) = \left(\frac{4}{7}\right) = 1, while 7 is not among the squares modulo 11.
Results
Throughout, p and q are distinct odd primes, \displaystyle m = \frac{p-1}{2} and \displaystyle h = \frac{q-1}{2}.
Theorem 1 (Eisenstein’s lemma). Let a be an odd integer with p \nmid a. Then
Theorem 2 (the lattice count). T(q, p) + T(p, q) = mh.
Theorem 3 (the law of quadratic reciprocity). \displaystyle \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{mh}.
Corollary 4. Let q^{*} = (-1)^{h} q. Then \displaystyle \left(\frac{q^{*}}{p}\right) = \left(\frac{p}{q}\right). Consequently, if p' is an odd prime other than q with p' \equiv p \pmod{4q}, then \displaystyle \left(\frac{q}{p'}\right) = \left(\frac{q}{p}\right); when q \equiv 1 \pmod 4, p' \equiv p \pmod q is enough.
Theorem 5 (rules for the Jacobi symbol). Let n and n' be odd positive integers and a, b integers. (a) If a \equiv b \pmod n, then \displaystyle \left(\frac{a}{n}\right) = \left(\frac{b}{n}\right). (b) \displaystyle \left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right) and \displaystyle \left(\frac{a}{nn'}\right) = \left(\frac{a}{n}\right)\left(\frac{a}{n'}\right). (c) \displaystyle \left(\frac{a}{n}\right) = 0 if \gcd(a, n) > 1, and \displaystyle \left(\frac{a}{n}\right) = \pm 1 otherwise. (d) If \gcd(a, n) = 1 and a is a square modulo n, then \displaystyle \left(\frac{a}{n}\right) = 1. So \displaystyle \left(\frac{a}{n}\right) = -1 proves that a is not a square modulo n.
Theorem 6 (reciprocity for the Jacobi symbol). Let n and n' be odd positive integers. Then \displaystyle \left(\frac{-1}{n}\right) = (-1)^{(n-1)/2} and \displaystyle \left(\frac{2}{n}\right) = (-1)^{(n^2-1)/8}, and if \gcd(n, n') = 1,
So a Legendre symbol can be evaluated by reducing the top, taking out factors -1 and 2, and flipping the odd part by Theorem 6, prime or not. The pairs shrink as in the The Euclidean algorithm and coprime numbers, nothing is factored, and the result is the Legendre symbol since p is prime.
Why it is true
Proof of Theorem 1. For 1 \le j \le m, divide ja by p: ja = p\lfloor ja/p \rfloor + r_j with 0 < r_j < p, where r_j \ne 0 because p \nmid ja by Euclid’s lemma. Let s_1, \dots, s_{\mu} be the r_j greater than \displaystyle \frac{p}{2} and t_1, \dots, t_{\nu} the others. The proof of Gauss’s lemma (Theorem 7 of Quadratic residues and the Legendre symbol) shows that t_1, \dots, t_{\nu}, p - s_1, \dots, p - s_{\mu} are 1, 2, \dots, m in some order, and that \displaystyle \left(\frac{a}{p}\right) = (-1)^{\mu}. Write \sigma for s_1 + \dots + s_{\mu} and \tau for t_1 + \dots + t_{\nu}. Summing the divisions over j, and summing the reordered list,
Subtracting gives (a - 1)\sum_{j=1}^{m} j = p\,(T(a, p) - \mu) + 2\sigma. As a is odd the left side is even, so p\,(T(a, p) - \mu) is even, and as p is odd, T(a, p) \equiv \mu \pmod 2. Hence \displaystyle \left(\frac{a}{p}\right) = (-1)^{\mu} = (-1)^{T(a, p)}. \square
Proof of Theorem 2. Let R be the set of lattice points (x, y) with 1 \le x \le m and 1 \le y \le h; it has mh points. None lies on the line py = qx: that would give p \mid qx, so p \mid x by Euclid’s lemma, impossible for 1 \le x < p. Fix x. Since \displaystyle \frac{qx}{p} is not an integer, the y \ge 1 with py < qx are 1, 2, \dots, \lfloor qx/p \rfloor, and all of them are at most h: from \displaystyle x \le m < \frac{p}{2} we get \displaystyle \frac{qx}{p} < \frac{q}{2}, and an integer below \displaystyle \frac{q}{2} is at most \displaystyle \frac{q-1}{2}. So R has \sum_{x=1}^{m} \lfloor qx/p \rfloor = T(q, p) points below the line. Exchanging the roles of (p, x) and (q, y), it has T(p, q) points above the line, and every point is on one side. \square
Proof of Theorem 3. The prime q is odd and p \nmid q, so Theorem 1 gives \displaystyle \left(\frac{q}{p}\right) = (-1)^{T(q, p)}; in the same way \displaystyle \left(\frac{p}{q}\right) = (-1)^{T(p, q)}. Multiply and apply Theorem 2. \square
Proof of Corollary 4. By the multiplicative rule and the rule for -1,
which is \displaystyle \left(\frac{p}{q}\right) by Theorem 3. Let p' \equiv p \pmod{4q}. Then p' \equiv p \pmod q, so \displaystyle \left(\frac{q^{*}}{p'}\right) = \left(\frac{p'}{q}\right) equals \displaystyle \left(\frac{p}{q}\right) = \left(\frac{q^{*}}{p}\right); and p' \equiv p \pmod 4, so \displaystyle \left(\frac{-1}{p'}\right) = \left(\frac{-1}{p}\right). Since q = (-1)^{h} q^{*}, multiplying gives \displaystyle \left(\frac{q}{p'}\right) = \left(\frac{q}{p}\right). If q \equiv 1 \pmod 4, then q = q^{*} and only p' \equiv p \pmod q was used. \square
Proof of Theorem 5. Let n = p_1 \cdots p_k. (a) a \equiv b modulo each p_i, so no factor changes. (b) Each Legendre symbol is multiplicative in its top; and the prime factors of nn' are those of n followed by those of n'. (c) A factor is 0 exactly when p_i \mid a, which happens for some i exactly when \gcd(a, n) > 1; otherwise every factor is \pm 1. (d) If a \equiv x^2 \pmod n, then a \equiv x^2 \pmod{p_i} with p_i \nmid a, so every factor is 1. \square
Proof of Theorem 6. For odd u put \displaystyle f(u) = \frac{u-1}{2} and \displaystyle g(u) = \frac{u^2-1}{8}, an integer since u^2 - 1 = (u - 1)(u + 1) is a product of consecutive even numbers. For odd u, v,
The first is even since 4 \mid (u-1)(v-1), the second since 64 \mid (u^2-1)(v^2-1). So by induction on k, f(p_1 \cdots p_k) \equiv \sum_i f(p_i) \pmod 2, and the same for g (for n = 1 the product is empty and f(1) = g(1) = 0). The supplementary laws give \displaystyle \left(\frac{-1}{n}\right) = \prod_i (-1)^{f(p_i)} = (-1)^{f(n)} and \displaystyle \left(\frac{2}{n}\right) = \prod_i (-1)^{g(p_i)} = (-1)^{g(n)}. For the last claim let n' = q_1 \cdots q_l. As \gcd(n, n') = 1, no p_i equals any q_j, so Theorem 5(b) and Theorem 3 give
since the exponents add to \left(\sum_i f(p_i)\right)\left(\sum_j f(q_j)\right) \equiv f(n) f(n') modulo 2. \square
Worked examples
Flipping once
Evaluate \displaystyle \left(\frac{59}{83}\right).
SolutionBoth 59 = 4 \cdot 14 + 3 and 83 = 4 \cdot 20 + 3 are primes \equiv 3 \pmod 4, so Theorem 3 flips the symbol with a change of sign, and then the top is reduced modulo 59:
As 24 = 2^2 \cdot 6, the square factor drops out and \displaystyle \left(\frac{24}{59}\right) = \left(\frac{2}{59}\right)\left(\frac{3}{59}\right). Since 59 \equiv 3 \pmod 8, \displaystyle \left(\frac{2}{59}\right) = -1. Both 3 and 59 are \equiv 3 \pmod 4, so \displaystyle \left(\frac{3}{59}\right) = -\left(\frac{59}{3}\right) = -\left(\frac{2}{3}\right) = 1. Hence \displaystyle \left(\frac{24}{59}\right) = -1 and \displaystyle \left(\frac{59}{83}\right) = 1: 59 is a square modulo 83. Check: running through 59, 142, 225, the numbers \equiv 59 \pmod{83}, gives 225 = 15^2, so the square roots are x \equiv 15, 68 \pmod{83}.
A top with three prime factors
Decide whether 442 is a square modulo the prime 1009.
SolutionFactor 442 = 2 \cdot 13 \cdot 17 and use multiplicativity. Since 1009 = 8 \cdot 126 + 1, \displaystyle \left(\frac{2}{1009}\right) = 1, and as 1009 \equiv 1 \pmod 4 every flip keeps its sign. With 1009 = 77 \cdot 13 + 8 and 13 \equiv 5 \pmod 8,
With 1009 = 59 \cdot 17 + 6, 17 \equiv 1 \pmod 8 and 17 \equiv 2 \pmod 3,
So \displaystyle \left(\frac{442}{1009}\right) = 1 \cdot (-1)(-1) = 1, and 442 is a square modulo 1009. Reciprocity says a root exists without producing one; a search finds x \equiv 253, and indeed 253^2 = 64{,}009 = 63 \cdot 1009 + 442.
Flipping without factoring
Naomi asks Andre whether 2819 is a square modulo the prime 4177. Euler’s criterion would need 2819^{2088} modulo 4177. Answer with the Jacobi symbol instead.
SolutionEach step below is Theorem 5(a) (reduce the top), the rule for 2 in Theorem 6, or the flip of Theorem 6, which changes sign only when both entries are \equiv 3 \pmod 4:
In order: 4177 \equiv 1 \pmod 4 and 4177 - 2819 = 1358 = 2 \cdot 679, with 2819 \equiv 3 \pmod 8. The pairs 679, 2819 and 103, 679 are both \equiv 3 \pmod 4, with 2819 = 4 \cdot 679 + 103 and 679 = 6 \cdot 103 + 61. Next 61 \equiv 1 \pmod 4, 103 = 61 + 42 and 61 \equiv 5 \pmod 8. Finally 21 \equiv 1 \pmod 4, 61 = 2 \cdot 21 + 19, 21 = 19 + 2 and 19 \equiv 3 \pmod 8.
Since 4177 is prime, the Jacobi symbol is the Legendre symbol, and 2819 is not a square modulo 4177. The tops 679 = 7 \cdot 97 and 21 = 3 \cdot 7 were flipped without being factored.
The primes for which 7 is a square
Find every odd prime p \ne 7 for which 7 is a quadratic residue, as congruence classes modulo 28.
SolutionAs 7 \equiv 3 \pmod 4, Theorem 3 gives \displaystyle \left(\frac{7}{p}\right) = (-1)^{(p-1)/2}\left(\frac{p}{7}\right). The squares modulo 7 are 1, 2, 4. So \displaystyle \left(\frac{7}{p}\right) = 1 exactly when p \equiv 1 \pmod 4 and p \equiv 1, 2, 4 \pmod 7, or p \equiv 3 \pmod 4 and p \equiv 3, 5, 6 \pmod 7. Among 1, 5, 9, 13, 17, 21, 25, the classes \equiv 1 \pmod 4 modulo 28, those \equiv 1, 2, 4 \pmod 7 are 1, 9, 25; among 3, 7, 11, 15, 19, 23, 27, those \equiv 3, 5, 6 \pmod 7 are 3, 19, 27. So
that is, p \equiv \pm 1, \pm 3, \pm 9 \pmod{28}: whole classes modulo 28, as Corollary 4 predicts. Check: p = 19 has 8^2 = 64 = 3 \cdot 19 + 7, while p = 5 is excluded and 7 \equiv 2 is indeed not a square modulo 5.
A proof: infinitely many primes of the form 3k + 1
Prove that there are infinitely many primes p \equiv 1 \pmod 3.
SolutionProof. First, for a prime p > 3, Corollary 4 with q = 3, q^{*} = -3 gives \displaystyle \left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right), which is 1 exactly when p \equiv 1 \pmod 3.
Suppose q_1, \dots, q_k are all the primes \equiv 1 \pmod 3 (7 is one), let Q = q_1 \cdots q_k and N = (2Q)^2 + 3. Then N is odd, and 3 \nmid N, since otherwise 3 \mid (2Q)^2 and 3 \mid Q by Euclid’s lemma. Let p be a prime factor of N; then p > 3 and (2Q)^2 \equiv -3 \pmod p, so \displaystyle \left(\frac{-3}{p}\right) = 1 and p \equiv 1 \pmod 3. So p = q_i for some i, and p divides both N and (2Q)^2, hence 3, a contradiction. \square
Pépin’s test
For k \ge 1 let F_k = 2^{2^k} + 1. Prove that F_k is prime if and only if 3^{(F_k - 1)/2} \equiv -1 \pmod{F_k}.
SolutionProof. Write F = F_k. Suppose F is prime. As 2^k \ge 2, 4 \mid 2^{2^k} and F \equiv 1 \pmod 4; as 2^{2^k} = 4^{2^{k-1}} \equiv 1 \pmod 3, F \equiv 2 \pmod 3. So Theorem 3 gives \displaystyle \left(\frac{3}{F}\right) = \left(\frac{F}{3}\right) = \left(\frac{2}{3}\right) = -1, and Euler’s criterion gives 3^{(F-1)/2} \equiv -1 \pmod F.
Conversely, suppose 3^{(F-1)/2} \equiv -1 \pmod F, and let p be a prime factor of F, odd since F is. Then 3^{F-1} \equiv 1 and 3^{(F-1)/2} \equiv -1 \not\equiv 1 \pmod p. So \operatorname{ord}_p(3) divides F - 1 = 2^{2^k} but not \displaystyle \frac{F-1}{2} (Primitive roots): it is a power of 2 that does not divide 2^{2^k - 1}, so it is 2^{2^k} = F - 1. As the order divides p - 1, F - 1 \le p - 1, so p \ge F and F = p is prime. \square
For F_2 = 17: 3^8 = 6561 = 386 \cdot 17 - 1 \equiv -1, so 17 is prime. A computer finds that 3^{(F_5 - 1)/2} \not\equiv -1 modulo F_5 = 4{,}294{,}967{,}297, which proves F_5 composite without a factor; in fact F_5 = 641 \cdot 6{,}700{,}417.
Boundaries
- Distinct odd primes. The law needs p \ne q (then \displaystyle \left(\frac{p}{p}\right) = 0) and both odd; the prime 2 is handled by the rule \displaystyle \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} instead.
- The Jacobi symbol is not a residue test. Theorem 5(d) runs one way only: \displaystyle \left(\frac{3}{35}\right) = \left(\frac{3}{5}\right)\left(\frac{3}{7}\right) = (-1)(-1) = 1, yet 3 is not a square modulo 5, so not modulo 35. Only a prime bottom makes the value 1 mean “square”. The bottom must be odd and positive.
- Odd tops in Eisenstein’s lemma. Theorem 1 fails for even a (Exercise 18).
- Existence, not a root. Reciprocity decides whether x^2 \equiv a \pmod p is solvable without finding x (Example 2).
- Higher powers. Cubic and quartic reciprocity laws exist, but they live in the rings \mathbb{Z}[\omega] and \mathbb{Z}[i], beyond this course.
Where this goes next
The Jacobi symbol is fast to compute, and that drives the Solovay-Strassen primality test: for odd n and \gcd(a, n) = 1, a prime n always satisfies \displaystyle a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n, and for composite n at most half of the a do, a bound stated here without proof; compare RSA and primality tests. Sums of two squares uses only the symbol of -1. A second proof of reciprocity, through Gauss sums in a finite field, opens algebraic number theory, where the law describes how primes factor in quadratic rings.
Exercises
Evaluating symbols
- Evaluate \displaystyle \left(\frac{13}{71}\right).
- Evaluate \displaystyle \left(\frac{-21}{97}\right).
- Evaluate \displaystyle \left(\frac{385}{997}\right).
- Decide whether x^2 \equiv 165 \pmod{191} has a solution.
- Decide how many solutions x^2 + 5x + 11 \equiv 0 \pmod{197} has.
- Evaluate \displaystyle \left(\frac{3001}{5003}\right) with the Jacobi symbol, factoring no top.
Which primes
- Find every odd prime p \ne 11 for which 11 is a quadratic residue, as classes modulo 44.
- List the odd primes p < 100, p \ne 13, for which 13 is a quadratic residue.
- Show that 6 is a quadratic residue modulo a prime p > 3 exactly when p \equiv \pm 1, \pm 5 \pmod{24}.
- Find every prime p < 60 that divides n^2 + n + 2 for some integer n.
The Jacobi symbol
- Evaluate \displaystyle \left(\frac{11}{63}\right), and decide whether 11 is a square modulo 63.
- The number 7919 is prime. Decide whether 2021 is a square modulo 7919 without factoring 2021.
- List the a with 1 \le a < 21, \gcd(a, 21) = 1 and \displaystyle \left(\frac{a}{21}\right) = 1, and say which of them are not squares modulo 21.
Proofs
- Let p and q be distinct primes, both \equiv 3 \pmod 4. Prove that exactly one of x^2 \equiv p \pmod q and x^2 \equiv q \pmod p has a solution.
- Let p and q = p + 4 both be odd primes. Prove that \displaystyle \left(\frac{q}{p}\right) = 1, that \displaystyle \left(\frac{p}{q}\right) = 1 exactly when p \equiv 1 \pmod 4, and that this agrees with Theorem 3.
- Prove that there are infinitely many primes p \equiv \pm 1 \pmod 5. (Consider 5(2Q)^2 - 1.)
- Prove that for k \ge 2, F_k = 2^{2^k} + 1 is prime if and only if 5^{(F_k - 1)/2} \equiv -1 \pmod{F_k}.
- Show that Theorem 1 fails for a = 2 and p = 5, and name the step of its proof that needs a odd.
- Let p be an odd prime and p \nmid a. Prove that \displaystyle \left(\frac{a}{p^2}\right) = 1, and show that 2 is not a square modulo 9.
- Let n > 1 be an odd positive integer that is not a perfect square. Prove that \displaystyle \sum_{a=0}^{n-1} \left(\frac{a}{n}\right) = 0.
Answers
- -1. As 13 \equiv 1 \pmod 4, flips keep their sign: \displaystyle \left(\frac{13}{71}\right) = \left(\frac{71}{13}\right) = \left(\frac{6}{13}\right). Here \displaystyle \left(\frac{2}{13}\right) = -1 as 13 \equiv 5 \pmod 8, and \displaystyle \left(\frac{3}{13}\right) = \left(\frac{13}{3}\right) = 1.
- -1. 97 \equiv 1 \pmod 8, so \displaystyle \left(\frac{-1}{97}\right) = 1 and every flip keeps its sign. \displaystyle \left(\frac{3}{97}\right) = \left(\frac{97}{3}\right) = 1 and \displaystyle \left(\frac{7}{97}\right) = \left(\frac{6}{7}\right) = \left(\frac{2}{7}\right)\left(\frac{3}{7}\right), which is 1 \cdot (-1) since \displaystyle \left(\frac{3}{7}\right) = -\left(\frac{7}{3}\right) = -1.
- -1. 385 = 5 \cdot 7 \cdot 11 and 997 \equiv 1 \pmod 4, so each flip keeps its sign. \displaystyle \left(\frac{5}{997}\right) = \left(\frac{2}{5}\right) = -1, as 997 = 199 \cdot 5 + 2; \displaystyle \left(\frac{7}{997}\right) = \left(\frac{3}{7}\right) = -1, as 997 = 142 \cdot 7 + 3; \displaystyle \left(\frac{11}{997}\right) = \left(\frac{7}{11}\right) = -\left(\frac{4}{7}\right) = -1, as 997 = 90 \cdot 11 + 7. The product of three -1s is -1.
- No solution: \displaystyle \left(\frac{165}{191}\right) = -1. Here 191 \equiv 7 \pmod 8. \displaystyle \left(\frac{3}{191}\right) = -\left(\frac{191}{3}\right) = -\left(\frac{2}{3}\right) = 1; \displaystyle \left(\frac{5}{191}\right) = \left(\frac{1}{5}\right) = 1; \displaystyle \left(\frac{11}{191}\right) = -\left(\frac{4}{11}\right) = -1, as 191 = 17 \cdot 11 + 4.
- Two solutions. Multiplying by 4 gives (2x + 5)^2 \equiv 25 - 44 = -19. As 197 \equiv 1 \pmod 4, \displaystyle \left(\frac{-19}{197}\right) = \left(\frac{197}{19}\right) = \left(\frac{7}{19}\right), and \displaystyle \left(\frac{7}{19}\right) = -\left(\frac{5}{7}\right) = -\left(\frac{2}{5}\right) = 1. Each of the two square roots gives one x; a search finds x \equiv 44, 148 \pmod{197}.
- 1. 3001 \equiv 1 \pmod 8, so the symbol is \displaystyle \left(\frac{2002}{3001}\right) = \left(\frac{1001}{3001}\right). As 1001 \equiv 1 \pmod 4, this is \displaystyle \left(\frac{999}{1001}\right) = \left(\frac{1001}{999}\right) = \left(\frac{2}{999}\right), which is 1 as 999 \equiv 7 \pmod 8.
- p \equiv \pm 1, \pm 5, \pm 7, \pm 9, \pm 19 \pmod{44}. By Theorem 3, \displaystyle \left(\frac{11}{p}\right) = (-1)^{(p-1)/2}\left(\frac{p}{11}\right), and the squares modulo 11 are 1, 3, 4, 5, 9. The classes \equiv 1 \pmod 4 whose remainder modulo 11 is a square are 1, 5, 9, 25, 37; the classes \equiv 3 \pmod 4 whose remainder is a nonsquare are 7, 19, 35, 39, 43.
- 3, 17, 23, 29, 43, 53, 61, 79. As 13 \equiv 1 \pmod 4, \displaystyle \left(\frac{13}{p}\right) = \left(\frac{p}{13}\right), so these are the primes whose remainder modulo 13 is among 1, 3, 4, 9, 10, 12.
- \displaystyle \left(\frac{6}{p}\right) = \left(\frac{2}{p}\right)\left(\frac{3}{p}\right). By Theorem 3, \displaystyle \left(\frac{3}{p}\right) = (-1)^{(p-1)/2}\left(\frac{p}{3}\right) is 1 exactly when p \equiv \pm 1 \pmod{12}, and \displaystyle \left(\frac{2}{p}\right) = 1 exactly when p \equiv \pm 1 \pmod 8. The product is 1 when both agree: of the classes 1, 5, 7, 11, 13, 17, 19, 23 modulo 24, that leaves 1, 5, 19, 23, that is, \pm 1, \pm 5.
- 2, 7, 11, 23, 29, 37, 43, 53. Every value n(n + 1) + 2 is even. For odd p, multiplying by 4 gives (2n + 1)^2 \equiv -7 \pmod p; p = 7 divides 3^2 + 3 + 2 = 14, and otherwise \displaystyle \left(\frac{-7}{p}\right) = \left(\frac{p}{7}\right) by Corollary 4, so p \equiv 1, 2, 4 \pmod 7.
- \displaystyle \left(\frac{11}{63}\right) = 1, but 11 is not a square modulo 63. As 63 = 3^2 \cdot 7, \displaystyle \left(\frac{11}{63}\right) = \left(\frac{11}{3}\right)^2\left(\frac{11}{7}\right) = \left(\frac{4}{7}\right). A square root modulo 63 would be one modulo 9, but 11 \equiv 2 and the squares of the units modulo 9 are 1, 4, 7.
- Yes, \displaystyle \left(\frac{2021}{7919}\right) = 1. 2021 \equiv 1 \pmod 4 and 7919 = 3 \cdot 2021 + 1856, with 1856 = 2^6 \cdot 29, so the symbol is \displaystyle \left(\frac{29}{2021}\right) = \left(\frac{20}{29}\right), as 2021 = 69 \cdot 29 + 20. Then \displaystyle \left(\frac{20}{29}\right) = \left(\frac{5}{29}\right) = \left(\frac{4}{5}\right) = 1.
- 1, 4, 5, 16, 17, 20; of these 5, 17, 20 are not squares. Here \displaystyle \left(\frac{a}{21}\right) = \left(\frac{a}{3}\right)\left(\frac{a}{7}\right) is 1 when both factors agree. The squares of the twelve units modulo 21 are only 1, 4, 16; for 5, 17 and 20 both factors are -1.
- Proof. As p \equiv q \equiv 3 \pmod 4, Theorem 3 gives \displaystyle \left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right), so exactly one of the two symbols is 1, and a congruence x^2 \equiv c modulo a prime not dividing c is solvable exactly when the symbol is 1. \square
- Proof. \displaystyle \left(\frac{q}{p}\right) = \left(\frac{4}{p}\right) = 1, since 4 = 2^2. Next \displaystyle \left(\frac{p}{q}\right) = \left(\frac{-4}{q}\right) = \left(\frac{-1}{q}\right) = (-1)^{(q-1)/2}, and q \equiv p \pmod 4, so it is 1 exactly when p \equiv 1 \pmod 4. Theorem 3 agrees: the product \displaystyle \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) is -1 exactly when both primes are \equiv 3 \pmod 4, which happens exactly when p \equiv 3 \pmod 4. \square
- Proof. As 5 \equiv 1 \pmod 4, \displaystyle \left(\frac{5}{p}\right) = \left(\frac{p}{5}\right) for odd p \ne 5, which is 1 exactly when p \equiv \pm 1 \pmod 5. Suppose q_1, \dots, q_k are all such primes (11 is one), Q = q_1 \cdots q_k and N = 5(2Q)^2 - 1 > 1. N is odd and N \equiv -1 \pmod 5. Let p be a prime factor of N; then p is odd, p \ne 5 and p \nmid 2Q (else p \mid 1). Let c be an inverse of 2Q modulo p. From 5(2Q)^2 \equiv 1 we get 5 \equiv c^2 \pmod p, so \displaystyle \left(\frac{5}{p}\right) = 1 and p \equiv \pm 1 \pmod 5, so p is some q_i and divides Q, a contradiction. \square
- Proof. Let F = F_k. For k \ge 2, 4 \mid 2^k, so 2^{2^k} = 16^{2^{k-2}} \equiv 1 \pmod 5 and F \equiv 2 \pmod 5; also F \equiv 1 \pmod 4. If F is prime, \displaystyle \left(\frac{5}{F}\right) = \left(\frac{F}{5}\right) = \left(\frac{2}{5}\right) = -1, and Euler’s criterion gives 5^{(F-1)/2} \equiv -1. Conversely, suppose 5^{(F-1)/2} \equiv -1 \pmod F and let p be an odd prime factor of F. Then 5^{(F-1)/2} \not\equiv 1 \pmod p, so \operatorname{ord}_p(5) divides F - 1 = 2^{2^k} but not \displaystyle \frac{F-1}{2}, hence equals F - 1. It divides p - 1, so p \ge F and p = F. \square
- For p = 5, m = 2 and T(2, 5) = \lfloor 2/5 \rfloor + \lfloor 4/5 \rfloor = 0, so the formula would give 1, but \displaystyle \left(\frac{2}{5}\right) = -1. The proof needs a odd to make (a - 1)\sum j even; for a = 2 it is \sum j = 3, odd.
- Proof. By definition \displaystyle \left(\frac{a}{p^2}\right) = \left(\frac{a}{p}\right)^2, and \displaystyle \left(\frac{a}{p}\right) = \pm 1 as p \nmid a, so the square is 1. For a = 2, p = 3: the units modulo 9 square to 1, 4, 7, 7, 4, 1 (for 1, 2, 4, 5, 7, 8), so 2 is not a square modulo 9 although \displaystyle \left(\frac{2}{9}\right) = 1. \square
- Proof. As n is not a square, some prime p divides n to an odd power e; write n = p^e n' with p \nmid n'. Take c with \displaystyle \left(\frac{c}{p}\right) = -1 (half the units are nonresidues, Theorem 2 of Quadratic residues and the Legendre symbol) and, by the The Chinese remainder theorem, b with b \equiv c \pmod p and b \equiv 1 \pmod{n'}. By Theorem 5, \displaystyle \left(\frac{b}{n}\right) = \left(\frac{c}{p}\right)^e\left(\frac{1}{n'}\right) = -1, and \gcd(b, n) = 1. As a runs over 0, \dots, n - 1, so does ba \bmod n, since b is invertible modulo n. So the sum S satisfies \displaystyle S = \sum_a \left(\frac{ba}{n}\right) = \left(\frac{b}{n}\right) S = -S, and S = 0. \square