Contents / Number Theory / Classical Theorems

Chapter 3

Classical Theorems

Fermat's little theorem proved twice, by rearranging residues and via Lagrange; Euler's generalisation; Wilson's theorem in both directions; why the Fermat primality test fails, with Korselt's criterion and 561 worked; and quadratic reciprocity proved in full through Gauss's lemma and Eisenstein's lattice-point count, with both supplementary laws.

Introduction

Three theorems carry most of the weight of elementary number theory, and this chapter proves all three. Fermat's little theorem says that raising to the power $p - 1$ modulo a prime $p$ always returns $1$ ; Wilson's theorem evaluates the factorial $(p - 1)!$ modulo $p$ exactly, and does so in a way that detects primality; and quadratic reciprocity relates the solvability of $x^{2} \equiv q (mod p)$ to the solvability of $x^{2} \equiv p (mod q)$ , a symmetry between two unrelated-looking questions that Gauss called the theorema aureum and proved eight times.

What ties them together is a single technique, used over and over: take a finite set of residues, act on it by multiplication, and observe that the action only permutes the set. Nothing is created or destroyed, so the product of the set is unchanged, and comparing the two expressions for that product yields a congruence. Fermat's little theorem is that argument applied to multiplication by $a$ ; Wilson's theorem is that argument applied to inversion; Gauss's lemma is that argument applied to multiplication by $a$ on a half-system of residues. Once the pattern is visible, the chapter is one idea told three times, each time with a sharper conclusion.

The chapter is a proof showcase, so almost every statement below is proved rather than quoted. The two exceptions are flagged where they occur: the sign of the quadratic Gauss sum, which needs analysis outside the scope of these pages, and one alternative route to reciprocity that is given as an explicitly labelled sketch. Everything else — including quadratic reciprocity itself, via Gauss's lemma and Eisenstein's lattice-point count — is argued in full.

We assume the language of congruences and the structure of $(Z / n Z)^{\times}$ as developed in Modular Arithmetic, and the multiplicativity of Euler's totient from Arithmetic Functions. From abstract algebra we shall use Lagrange's theorem once, by name, and note carefully where the elementary argument replaces it.

Throughout, $p$ and $q$ denote odd primes unless stated otherwise, $n$ a positive integer, and $g cd$ the greatest common divisor.

3.1Fermat's Little Theorem: Statement and First Proof

The theorem has two forms. The first is the one that does the work; the second is the one that is true without exception, and the two are equivalent in a single line.

Theorem 3.1 (Fermat's little theorem). Let $p$ be a prime and let $a$ be an integer with $g cd (a, p) = 1$ . Then

a^{p - 1} \equiv 1 (mod p) .

Proof. Consider the $p - 1$ numbers

a, 2 a, 3 a, \dots, (p - 1) a

reduced modulo $p$ . Two claims about this list.

Every entry is nonzero modulo $p$ . If $p ∣ ia$ for some $1 \leq i \leq p - 1$ then, $p$ being prime, $p ∣ i$ or $p ∣ a$ . The first is impossible because $0 < i < p$ , and the second contradicts $g cd (a, p) = 1$ .

The entries are pairwise distinct modulo $p$ . If $ia \equiv ja (mod p)$ then $p ∣ (i - j) a$ , and as $p ∤ a$ we get $p ∣ i - j$ ; since $∣ i - j ∣ < p - 1 < p$ this forces $i = j$ .

So the list consists of $p - 1$ distinct nonzero residues modulo $p$ . There are exactly $p - 1$ such residues, namely $1, 2, \dots, p - 1$ , so the list is that set, merely rearranged. Multiplying all the entries of a set does not depend on the order in which they are listed, so

a \cdot 2 a \dots (p - 1) a \equiv 1 \cdot 2 \dots (p - 1) (mod p),

that is,

a^{p - 1} (p - 1)! \equiv (p - 1)! (mod p) .

Finally $(p - 1)!$ is a product of integers none of which is divisible by $p$ , so $g cd ((p - 1)!, p) = 1$ and we may cancel it from both sides, leaving $a^{p - 1} \equiv 1 (mod p)$ .∎

The last step is where primality is used a second time, and it is worth pausing on: cancelling a factor from a congruence is legal only when that factor is invertible modulo the modulus. The argument is a template — permute, multiply, cancel — and every other theorem in this chapter is a variation on it.

Corollary 3.2 (Universal form). For every prime $p$ and every integer $a$ ,

a^{p} \equiv a (mod p) .

Proof. If $g cd (a, p) = 1$ , multiply the congruence of the theorem Fermat's little theorem through by $a$ . If instead $p ∣ a$ , then $p ∣ a^{p}$ as well, so both sides are $\equiv 0 (mod p)$ and the congruence holds trivially. Since $p$ is prime these two cases are exhaustive.∎

Pitfall. The first form genuinely needs $g cd (a, p) = 1$ : with $p = 5$ , $a = 10$ we have $1 0^{4} \equiv 0 (mod 5)$ , not $1$ . Only the universal form survives without the hypothesis. A student who remembers "the exponent is $p - 1$ " and forgets the coprimality has a statement that is false for a positive proportion of inputs.

Intuition. Multiplying by a fixed invertible $a$ shuffles the deck of nonzero residues without losing a card. Do it $p - 1$ times and the running product of the whole deck has been multiplied by $a^{p - 1}$ — but the deck is the same deck, so its product never changed. Hence $a^{p - 1}$ must have been $1$ all along.

Example 3.3 (Both forms for $p = 7$ , $a = 3$ ). Verify $3^{6} \equiv 1 (mod 7)$ and $3^{7} \equiv 3 (mod 7)$ by hand.

Solution.

Square up: $3^{2} = 9 \equiv 2$ , so $3^{4} \equiv 2^{2} = 4$ , and $3^{6} = 3^{4} \cdot 3^{2} \equiv 4 \cdot 2 = 8 \equiv 1 (mod 7)$ .
Multiplying by $3$ gives $3^{7} \equiv 3 (mod 7)$ , the universal form.
As a check on the proof, the shuffled list $3, 6, 9, 12, 15, 18$ reduces mod $7$ to $3, 6, 2, 5, 1, 4$ — the residues $1$ through $6$ in a new order, exactly as the argument claims.

□

Exercises for §3.1 →

3.2Fermat via Lagrange, and Euler's Generalisation

The elementary proof above is self-contained, but it hides the reason the exponent is $p - 1$ . That reason is structural: $p - 1$ is the size of a group, and a general theorem says the size of a group annihilates each of its elements.

Definition 3.4 (Multiplicative order). Let $g cd (a, n) = 1$ . The order of $a$ modulo $n$ , written $ord_{n} (a)$ , is the least positive integer $d$ with

a^{d} \equiv 1 (mod n) .

It exists because the powers $a, a^{2}, a^{3}, \dots$ take finitely many values, so $a^{i} \equiv a^{j}$ for some $i < j$ , and cancelling the invertible $a^{i}$ gives $a^{j - i} \equiv 1$ .

Proposition 3.5 (The order divides every annihilating exponent). Let $g cd (a, n) = 1$ and $d = ord_{n} (a)$ . For an integer $m \geq 1$ ,

a^{m} \equiv 1 (mod n) ⟺ d ∣ m .

Proof. ( $\Leftarrow$ ) If $m = d k$ then $a^{m} = (a^{d})^{k} \equiv 1^{k} = 1$ .

( $\Rightarrow$ ) Divide with remainder: $m = d k + r$ with $0 \leq r < d$ . Then

1 \equiv a^{m} = (a^{d})^{k} a^{r} \equiv a^{r} (mod n) .

So $a^{r} \equiv 1$ with $0 \leq r < d$ . Minimality of $d$ among positive exponents forces $r = 0$ , hence $d ∣ m$ .∎

Theorem 3.6 (Fermat's little theorem, second proof). Let $p$ be prime and $g cd (a, p) = 1$ . Then $a^{p - 1} \equiv 1 (mod p)$ .

Proof. The set $(Z / p Z)^{*}$ of nonzero residue classes modulo $p$ is a group under multiplication: it is closed because $p$ is prime and therefore has no zero divisors, associativity and the identity are inherited from $Z$ , and each class $[b]$ with $p ∤ b$ has an inverse because $g cd (b, p) = 1$ gives $b x + p y = 1$ for some integers $x, y$ , whence $b x \equiv 1 (mod p)$ . Its order is $∣ (Z / p Z)^{*} ∣ = p - 1$ .

The cyclic subgroup $⟨[a]⟩$ generated by $[a]$ has exactly $d = ord_{p} (a)$ elements, namely $[a], [a]^{2}, \dots, [a]^{d} = [1]$ , which are pairwise distinct: if $[a]^{i} = [a]^{j}$ with $1 \leq i < j \leq d$ then $[a]^{j - i} = [1]$ with $0 < j - i < d$ , contradicting minimality.

By Lagrange's theorem, the order of a subgroup divides the order of the group, so $d ∣ p - 1$ . By the proposition The order divides every annihilating exponent applied with $m = p - 1$ , we conclude $a^{p - 1} \equiv 1 (mod p)$ .∎

Remark. Compare the two proofs. The elementary one shows that $a^{p - 1} \equiv 1$ ; the group-theoretic one shows why the exponent is $p - 1$ and immediately tells you more — that the true exponent for a given $a$ is a divisor $d$ of $p - 1$ , and that $d$ is the size of the cyclic group $a$ generates. The elementary proof does not see the divisibility at all. This is the usual trade: the first argument is shorter, the second is a machine.

Once the exponent is identified as the size of the unit group, the generalisation to a composite modulus writes itself. Only the count changes.

Definition 3.7 (Euler's totient). For $n \geq 1$ , $φ (n)$ is the number of integers in ${1, 2, \dots, n}$ that are coprime to $n$ ; equivalently $φ (n) = ∣ (Z / n Z)^{*} ∣$ . For a prime power, $φ (p^{k}) = p^{k} - p^{k - 1}$ , and $φ$ is multiplicative on coprime arguments, as proved in Arithmetic Functions.

Theorem 3.8 (Euler's theorem). If $g cd (a, n) = 1$ then

a^{φ (n)} \equiv 1 (mod n) .

Proof. We repeat the rearrangement argument, with the reduced residue system in place of $1, \dots, p - 1$ . Let $r_{1}, r_{2}, \dots, r_{φ (n)}$ be the integers in ${1, \dots, n}$ coprime to $n$ , one from each invertible class.

The list $a r_{1}, \dots, a r_{φ (n)}$ again consists of classes coprime to $n$ : $g cd (a, n) = 1$ and $g cd (r_{i}, n) = 1$ give $g cd (a r_{i}, n) = 1$ .

The entries are pairwise distinct modulo $n$ : if $a r_{i} \equiv a r_{j}$ then, multiplying by an inverse of $a$ modulo $n$ (which exists since $g cd (a, n) = 1$ ), $r_{i} \equiv r_{j}$ , so $i = j$ .

So ${a r_{1}, \dots, a r_{φ (n)}}$ is a set of $φ (n)$ distinct invertible classes, hence all of them, and is a permutation of ${r_{1}, \dots, r_{φ (n)}}$ modulo $n$ . Taking products,

a^{φ (n)} i \prod r_{i} \equiv i \prod r_{i} (mod n) .

Each $r_{i}$ is invertible modulo $n$ , hence so is the product, and cancelling it gives the claim.∎

Corollary 3.9 (Euler implies Fermat). Taking $n = p$ prime in Euler's theorem recovers Fermat's little theorem.

Proof. For $p$ prime every one of $1, 2, \dots, p - 1$ is coprime to $p$ , so $φ (p) = p - 1$ , and the congruence $a^{φ (p)} \equiv 1$ becomes $a^{p - 1} \equiv 1$ .∎

Example 3.10 (An order computation). Find $ord_{13} (5)$ and check the divisibility predicted by Lagrange's theorem.

Solution.

The order must divide $φ (13) = 12$ , so it lies in ${1, 2, 3, 4, 6, 12}$ .
$5^{2} = 25 \equiv 12 \equiv - 1 (mod 13)$ . Since $5^{2} \neq = 1$ , the order is not $1$ or $2$ .
From $5^{2} \equiv - 1$ we get $5^{4} \equiv 1 (mod 13)$ , so the order divides $4$ ; combined with step 2 it is exactly $4$ .
Indeed $4 ∣ 12$ , as required, and $5^{12} = (5^{4})^{3} \equiv 1$ .

□

Example 3.11 (Inverses for free). Use Fermat's little theorem to invert $8$ modulo $29$ without the Euclidean algorithm.

Solution.

Since $29$ is prime and $29 ∤ 8$ , we have $8^{28} \equiv 1 (mod 29)$ , so $8^{27}$ is the inverse of $8$ .
Compute by squaring: $8^{2} = 64 \equiv 6$ , $8^{4} \equiv 36 \equiv 7$ , $8^{8} \equiv 49 \equiv 20$ , $8^{16} \equiv 400 \equiv 400 - 377 = 23$ .
Then $27 = 16 + 8 + 2 + 1$ , so $8^{27} \equiv 23 \cdot 20 \cdot 6 \cdot 8 (mod 29)$ . Step by step: $23 \cdot 20 = 460 \equiv 460 - 435 = 25$ ; $25 \cdot 6 = 150 \equiv 150 - 145 = 5$ ; $5 \cdot 8 = 40 \equiv 11$ .
Check: $8 \cdot 11 = 88 = 3 \cdot 29 + 1 \equiv 1 (mod 29)$ . The inverse is $11$ .

□

Exercises for §3.2 →

3.3The Fermat Primality Test and Its Failure

Fermat's little theorem is a statement about primes, so its contrapositive is a test for compositeness: if $a^{n - 1} \neq \equiv 1 (mod n)$ for some $a$ coprime to $n$ , then $n$ is certainly not prime. The test is cheap — one modular exponentiation — and it never lies in that direction. The question is what a pass is worth.

Definition 3.12 (Fermat witness and Fermat liar). Let $n > 1$ be composite and $g cd (a, n) = 1$ . The base $a$ is a Fermat witness for $n$ if

a^{n - 1} \neq \equiv 1 (mod n),

and a Fermat liar if $a^{n - 1} \equiv 1 (mod n)$ . If $n$ is composite and $a$ is a liar, $n$ is called a Fermat pseudoprime to base $a$ .

Example 3.13 (The smallest pseudoprime to base 2). Show that $n = 341 = 11 \cdot 31$ is a Fermat pseudoprime to base $2$ , and find a witness.

Solution.

$2^{10} = 1024 = 3 \cdot 341 + 1$ , so $2^{10} \equiv 1 (mod 341)$ .
Since $340 = 10 \cdot 34$ , we get $2^{340} = (2^{10})^{34} \equiv 1 (mod 341)$ : base $2$ is a liar and $341$ passes the test.
Try base $3$ . Modulo $11$ , $3^{340} = 3^{10 \cdot 34} \equiv 1$ ; modulo $31$ , $ord_{31} (3) = 30$ and $340 = 11 \cdot 30 + 10$ , so $3^{340} \equiv 3^{10} (mod 31)$ . Now $3^{3} = 27 \equiv - 4$ , $3^{5} \equiv - 4 \cdot 9 = - 36 \equiv - 5$ , $3^{10} \equiv 25 (mod 31)$ .
So $3^{340} \equiv 25 \neq \equiv 1 (mod 31)$ , hence $3^{340} \neq \equiv 1 (mod 341)$ : base $3$ is a witness and $341$ is exposed as composite.

□

That failure is repairable by trying more bases — provided witnesses are plentiful. The next proposition says that they are, in a strong sense, whenever there is even one.

Proposition 3.14 (Liars form a subgroup, so witnesses are abundant). Let $n$ be composite and let

L_{n} = {[a] \in (Z / n Z)^{*} : a^{n - 1} \equiv 1 (mod n)} .

Then $L_{n}$ is a subgroup of $(Z / n Z)^{*}$ . Consequently either $L_{n}$ is the whole group, or at most half of all coprime bases are liars.

Proof. $[1] \in L_{n}$ since $1^{n - 1} = 1$ . If $[a], [b] \in L_{n}$ then $(ab)^{n - 1} = a^{n - 1} b^{n - 1} \equiv 1 \cdot 1 = 1$ , so $[ab] \in L_{n}$ . And if $[a] \in L_{n}$ with inverse $[a]^{- 1}$ , then $(a^{- 1})^{n - 1} \equiv (a^{n - 1})^{- 1} \equiv 1$ , so $[a]^{- 1} \in L_{n}$ . Hence $L_{n}$ is a subgroup.

By Lagrange's theorem the index $[(Z / n Z)^{*} : L_{n}]$ divides $φ (n)$ and is at least $2$ as soon as $L_{n}$ is proper. Therefore $∣ L_{n} ∣ \leq φ (n) /2$ whenever a single witness exists.∎

So the test is excellent — a single random base exposes a composite with probability at least $1/2$ , and $k$ independent bases with probability at least $1 - 2^{- k}$ — except on the composites where $L_{n}$ is everything. Those exist.

Definition 3.15 (Carmichael number). A composite $n > 1$ is a Carmichael number if

a^{n - 1} \equiv 1 (mod n) for every a with g cd (a, n) = 1,

that is, if every coprime base is a liar and the Fermat test fails for $n$ no matter how many bases are tried.

Theorem 3.16 (Korselt's criterion). A composite $n$ is a Carmichael number if and only if $n$ is squarefree and

(p - 1) ∣ (n - 1) for every prime p ∣ n .

Proof. ( $\Leftarrow$ ) Suppose $n = p_{1} p_{2} \dots p_{k}$ with the $p_{i}$ distinct primes and $(p_{i} - 1) ∣ (n - 1)$ for each $i$ . Let $g cd (a, n) = 1$ ; then $p_{i} ∤ a$ for every $i$ . Write $n - 1 = (p_{i} - 1) m_{i}$ . By Fermat's little theorem,

a^{n - 1} = (a^{p_{i} - 1})^{m_{i}} \equiv 1 (mod p_{i})

for each $i$ . The $p_{i}$ are distinct primes whose product is $n$ , so a number congruent to $1$ modulo each of them is congruent to $1$ modulo $n$ . Hence $a^{n - 1} \equiv 1 (mod n)$ for every coprime $a$ .

( $\Rightarrow$ ) Suppose $n$ is Carmichael. We use the existence of primitive roots modulo $p^{e}$ for odd $p$ , from Modular Arithmetic.

$n$ is squarefree. Suppose not, so $n = p^{e} m$ with $e \geq 2$ and $g cd (p, m) = 1$ . Choose $g$ a primitive root modulo $p^{e}$ , so $ord_{p^{e}} (g) = φ (p^{e}) = p^{e - 1} (p - 1)$ , and use the Chinese remainder theorem to pick $a$ with $a \equiv g (mod p^{e})$ and $a \equiv 1 (mod m)$ . Then $g cd (a, n) = 1$ , so $a^{n - 1} \equiv 1 (mod n)$ and in particular modulo $p^{e}$ . By the proposition The order divides every annihilating exponent, $p^{e - 1} (p - 1) ∣ n - 1$ , so $p ∣ n - 1$ (using $e \geq 2$ ). But $p ∣ n$ , so $p ∣ n - (n - 1) = 1$ , absurd. (If $p = 2$ the same contradiction arrives faster: $4 ∣ n$ forces $n - 1$ odd while $φ (4) = 2$ must divide it.) Hence $n$ is squarefree.

The divisibility. Let $p ∣ n$ and write $n = \pm$ with $g cd (p, m) = 1$ , possible because $n$ is now known squarefree. Choose a primitive root $g$ modulo $p$ and, by the Chinese remainder theorem, an $a$ with $a \equiv g (mod p)$ and $a \equiv 1 (mod m)$ . Then $g cd (a, n) = 1$ , so $a^{n - 1} \equiv 1 (mod n)$ and hence modulo $p$ . Since $ord_{p} (a) = ord_{p} (g) = p - 1$ , the proposition The order divides every annihilating exponent gives $(p - 1) ∣ (n - 1)$ .∎

Example 3.17 (Why $561$ fools every base). Verify by Korselt's criterion that $561$ is a Carmichael number, and check the conclusion directly on the base $a = 2$ .

Solution.

Factor: $561 = 3 \cdot 11 \cdot 17$ . The three primes are distinct, so $561$ is squarefree.
$n - 1 = 560$ . Check each prime: $p = 3$ gives $p - 1 = 2$ and $560 = 2 \cdot 280$ ; $p = 11$ gives $10$ and $560 = 10 \cdot 56$ ; $p = 17$ gives $16$ and $560 = 16 \cdot 35$ . All three divide $560$ .
By Korselt's criterion $561$ is a Carmichael number: $a^{560} \equiv 1 (mod 561)$ for all $320$ coprime bases.
Direct check for $a = 2$ : modulo $3$ , $2^{560} = (2^{2})^{280} \equiv 1$ ; modulo $11$ , $2^{560} = (2^{10})^{56} \equiv 1$ ; modulo $17$ , $2^{560} = (2^{16})^{35} \equiv 1$ . Congruent to $1$ modulo $3$ , $11$ and $17$ , hence modulo their product $561$ .
Note that $561$ is nevertheless trivially composite — $3$ divides it. The Fermat test is blind to this because $3$ is not a coprime base, and the test only examines coprime bases.

□

Proposition 3.18 (A Carmichael number has at least three prime factors). No Carmichael number is a product of exactly two distinct primes.

Proof. Suppose $n = pq$ with $p < q$ primes were Carmichael. By Korselt's criterion $(q - 1) ∣ (n - 1)$ . Now

n - 1 = pq - 1 = p (q - 1) + (p - 1),

and $(q - 1) ∣ p (q - 1)$ , so $(q - 1) ∣ (p - 1)$ . But $0 < p - 1 < q - 1$ , and a positive integer cannot divide a smaller positive integer. Contradiction. Since Korselt's criterion also forces squarefreeness, a Carmichael number is a product of at least three distinct primes.∎

Figure 3.19. Fermat liars as a percentage of coprime bases. For ordinary composites the liars are a subgroup of index at least two, so the bar never exceeds

50%

; for the Carmichael numbers

561

and

1105

it reaches

100%

and the test is useless.

Pitfall. Passing the Fermat test to many bases is evidence of primality, never a proof. The Carmichael numbers are infinite in number, so no fixed finite set of bases makes the Fermat test into a primality proof. The repair is the Miller–Rabin test, which examines square roots of $1$ along the way and has no analogue of the Carmichael numbers.

Exercises for §3.3 →

3.4Reducing Exponents with Fermat and Euler

The practical content of the two theorems is that exponents live modulo $p - 1$ (or $φ (n)$ ), not modulo $n$ . This is the single most common working use of the chapter.

Proposition 3.20 (Exponent reduction). Let $g cd (a, n) = 1$ and let $k \equiv ℓ (mod φ (n))$ with $k, ℓ \geq 0$ . Then

a^{k} \equiv a^{ℓ} (mod n) .

In particular, for prime $p$ and $p ∤ a$ , $a^{k} \equiv a^{k mod (p - 1)} (mod p)$ .

Proof. Say $k \geq ℓ$ and write $k - ℓ = φ (n) t$ with $t \geq 0$ . By Euler's theorem,

a^{k} = a^{ℓ} (a^{φ (n)})^{t} \equiv a^{ℓ} \cdot 1^{t} = a^{ℓ} (mod n) .

The prime case is $φ (p) = p - 1$ .∎

Pitfall. The reduction is on the exponent modulo $φ (n)$ , and it needs $g cd (a, n) = 1$ . Reducing an exponent modulo $n$ instead is a common and disastrous slip: $2^{100} mod 7$ uses $100 \equiv 4 (mod 6)$ , not $100 \equiv 2 (mod 7)$ . The first gives $2^{4} \equiv 2$ , the second the wrong value $4$ .

Method 3.21 (Evaluating $a^{k} mod n$ by hand).

Check $g cd (a, n) = 1$ . If not, factor $n$ and work modulo each prime power separately.
Compute $φ (n)$ — for prime $n = p$ this is $p - 1$ .
Replace $k$ by $r = k mod φ (n)$ .
Compute $a^{r} mod n$ by repeated squaring, reducing after every multiplication.

Example 3.22 (A large power modulo a prime). Compute $7^{2026} mod 13$ .

Solution.

$13$ is prime and $13 ∤ 7$ , so exponents reduce modulo $12$ .
$2026 = 12 \cdot 168 + 10$ , so $7^{2026} \equiv 7^{10} (mod 13)$ .
$7^{2} = 49 \equiv 10$ , $7^{4} \equiv 1 0^{2} = 100 \equiv 9$ , $7^{8} \equiv 81 \equiv 3$ .
$7^{10} = 7^{8} \cdot 7^{2} \equiv 3 \cdot 10 = 30 \equiv 4 (mod 13)$ .

□

Example 3.23 (The last two digits of a tower). Find the last two digits of $7^{7^{7}}$ .

Solution.

The last two digits are the value modulo $100$ , and $φ (100) = 40$ , so we need the exponent $7^{7} = 823543$ modulo $40$ .
$φ (40) = 16$ and $g cd (7, 40) = 1$ , so $7^{7} \equiv 7^{7 mod 16} = 7^{7} (mod 40)$ — no reduction yet, so compute directly: $7^{2} = 49 \equiv 9$ , $7^{4} \equiv 81 \equiv 1 (mod 40)$ , hence $7^{7} = 7^{4} \cdot 7^{2} \cdot 7 \equiv 1 \cdot 9 \cdot 7 = 63 \equiv 23 (mod 40)$ .
So $7^{7^{7}} \equiv 7^{23} (mod 100)$ .
Compute: $7^{2} = 49$ , $7^{4} \equiv 4 9^{2} = 2401 \equiv 1 (mod 100)$ . Then $23 = 4 \cdot 5 + 3$ , so $7^{23} \equiv 7^{3} = 343 \equiv 43 (mod 100)$ .
The last two digits are $43$ .

□

Proposition 3.24 (Inversion by exponentiation). If $p$ is prime and $p ∤ a$ then $a^{p - 2}$ is the inverse of $a$ modulo $p$ ; more generally, if $g cd (a, n) = 1$ then $a^{φ (n) - 1}$ is the inverse of $a$ modulo $n$ .

Proof. $a \cdot a^{φ (n) - 1} = a^{φ (n)} \equiv 1 (mod n)$ by Euler's theorem, and an element with a right inverse in the commutative group $(Z / n Z)^{*}$ has that element as its inverse. For $n = p$ prime, $φ (p) - 1 = p - 2$ .∎

Remark. This is how a fixed-modulus implementation avoids the extended Euclidean algorithm: one exponentiation with a constant exponent is branch-free, which matters when the branches would leak the secret. It is also the identity that makes RSA decryption work — the decryption exponent $d$ satisfies $e d \equiv 1 (mod φ (n))$ , so $(m^{e})^{d} = m^{1 + φ (n) t} \equiv m (mod n)$ by the proposition Exponent reduction.

Exercises for §3.4 →

3.5Wilson's Theorem: Statement

Fermat's theorem evaluates a power modulo $p$ . Wilson's theorem evaluates a factorial modulo $p$ — and unlike Fermat's, it is an exact characterisation of the primes, with no Carmichael numbers to spoil it.

Theorem 3.25 (Wilson's theorem). Let $n > 1$ be an integer. Then

(n - 1)! \equiv - 1 (mod n) ⟺ n is prime .

The two directions are genuinely different arguments and are proved separately below: the forward direction in the section on pairing residues with their inverses, the converse by showing that a composite $n > 4$ makes $(n - 1)!$ divisible by $n$ outright. Before the proofs, some arithmetic to see what the statement is claiming.

Example 3.26 (Small cases by hand). Evaluate $(n - 1)! mod n$ for $n = 2, 3, 4, 5, 6, 7$ and read off the pattern.

Solution.

$n = 2$ : $1! = 1 \equiv 1 \equiv - 1 (mod 2)$ . Prime, and $- 1 \equiv 1$ here.
$n = 3$ : $2! = 2 \equiv - 1 (mod 3)$ . Prime.
$n = 4$ : $3! = 6 \equiv 2 (mod 4)$ . Composite — and note the value is $2$ , neither $- 1$ nor $0$ .
$n = 5$ : $4! = 24 \equiv - 1 (mod 5)$ . Prime.
$n = 6$ : $5! = 120 \equiv 0 (mod 6)$ . Composite.
$n = 7$ : $6! = 720 = 102 \cdot 7 + 6 \equiv - 1 (mod 7)$ . Prime.
The pattern: primes give $- 1$ , composites give $0$ , and $n = 4$ is the lone exception giving $2$ .

□

Remark. The case $n = 4$ is a real exception and must be stated. It is the only composite $n$ for which $(n - 1)!$ is not divisible by $n$ , because $3! = 6$ contains the factor $2$ only once while $4 = 2^{2}$ needs it twice. Every composite above $4$ has enough room below it, as the proof of the theorem Composite moduli kill the factorial makes precise.

Intuition. In the list $1, 2, \dots, p - 1$ every element has a multiplicative partner that cancels it. Pair everyone off and the whole product collapses to $1$ — except that two elements, $1$ and $p - 1$ , have no partner but themselves. Their product is $1 \cdot (p - 1) \equiv - 1$ , and that is the whole answer.

Exercises for §3.5 →

3.6Prime Implies the Congruence

The proof is the permute, multiply, cancel template again, with the permutation being inversion $x \mapsto x^{- 1}$ . The one thing to get right is which elements are fixed by that permutation.

Lemma 3.27 (Self-inverse residues modulo a prime). Let $p$ be prime and $1 \leq x \leq p - 1$ . Then

x^{2} \equiv 1 (mod p) ⟺ x \equiv 1 or x \equiv - 1 (mod p),

and for $p > 2$ these are the two distinct residues $1$ and $p - 1$ .

Proof. $x^{2} \equiv 1 (mod p)$ means $p ∣ x^{2} - 1 = (x - 1) (x + 1)$ . Since $p$ is prime, Euclid's lemma gives $p ∣ x - 1$ or $p ∣ x + 1$ , that is $x \equiv 1$ or $x \equiv - 1 (mod p)$ . Conversely both of those clearly square to $1$ .

For $p > 2$ the residues $1$ and $- 1 \equiv p - 1$ are distinct, since $1 \equiv - 1$ would mean $p ∣ 2$ . For $p = 2$ they coincide.∎

Pitfall. This lemma is exactly where primality enters, and it is exactly what fails for a composite modulus. Modulo $8$ the equation $x^{2} \equiv 1$ has four solutions, $x = 1, 3, 5, 7$ , because $8 ∣ (x - 1) (x + 1)$ can be arranged by splitting the two factors between $2$ and $4$ . A pairing argument run modulo $8$ therefore leaves four unpaired elements, not two, and gives a different answer.

Theorem 3.28 (Prime implies Wilson's congruence). If $p$ is prime then

(p - 1)! \equiv - 1 (mod p) .

Proof. For $p = 2$ the claim is $1! = 1 \equiv - 1 (mod 2)$ , true. Assume $p$ is odd.

Every $x \in {1, 2, \dots, p - 1}$ is coprime to $p$ , hence invertible modulo $p$ , and its inverse is again a residue in that range; write it $x^{- 1}$ . The map $x \mapsto x^{- 1}$ is a bijection of the set $S = {1, \dots, p - 1}$ onto itself, being its own inverse.

By the lemma Self-inverse residues modulo a prime, the only fixed points of this map — the $x$ with $x = x^{- 1}$ , equivalently $x^{2} \equiv 1$ — are $x = 1$ and $x = p - 1$ . Therefore the remaining $p - 3$ elements

S ∖ {1, p - 1} = {2, 3, \dots, p - 2}

are partitioned into $(p - 3) /2$ unordered pairs ${x, x^{- 1}}$ with $x \neq = x^{- 1}$ , each pair having product $x \cdot x^{- 1} \equiv 1 (mod p)$ . Note $p - 3$ is even because $p$ is odd, so the partition uses up every element.

Multiplying everything in $S$ therefore gives

(p - 1)! = 1 \cdot pairs \prod x x^{- 1} \cdot (p - 1) \equiv 1 \cdot 1^{(p - 3) /2} \cdot (p - 1) \equiv - 1 (mod p),

since $p - 1 \equiv - 1$ .∎

Figure 3.29. Inversion pairs up the residues modulo

13

. The ten residues

2, \dots, 11

fall into five arcs

{x, x^{- 1}}

, each contributing a factor

1

to the product; only

1

and

12 \equiv - 1

are fixed, so

12! \equiv 1 \cdot 12 \equiv - 1 (mod 13)

Corollary 3.30 (Value of $(p - 2)!$ ). For every prime $p$ ,

(p - 2)! \equiv 1 (mod p) .

Proof. $(p - 1)! = (p - 1) \cdot (p - 2)! \equiv - (p - 2)! (mod p)$ . By the theorem Prime implies Wilson's congruence the left side is $\equiv - 1$ , so $- (p - 2)! \equiv - 1$ and, multiplying by $- 1$ , $(p - 2)! \equiv 1 (mod p)$ .∎

Example 3.31 (Wilson in reverse). Compute $15! mod 17$ and $97! mod 101$ .

Solution.

$17$ is prime and $15 = 17 - 2$ , so by the corollary Value of $(p - 2)!$ , $15! \equiv 1 (mod 17)$ .
For the second, $101$ is prime, so $100! \equiv - 1 (mod 101)$ and $100! = 100 \cdot 99 \cdot 98 \cdot 97!$ .
Modulo $101$ : $100 \equiv - 1$ , $99 \equiv - 2$ , $98 \equiv - 3$ , so $100 \cdot 99 \cdot 98 \equiv - 6$ .
Thus $- 6 \cdot 97! \equiv - 1$ , i.e. $6 \cdot 97! \equiv 1 (mod 101)$ , so $97!$ is the inverse of $6$ .
$6 \cdot 17 = 102 \equiv 1 (mod 101)$ , so $97! \equiv 17 (mod 101)$ .

□

Exercises for §3.6 →

3.7The Converse: Composite Moduli

For the converse it is easier to prove something stronger than the negation of $(n - 1)! \equiv - 1$ : for composite $n > 4$ the factorial is not merely different from $- 1$ , it is $0$ .

Theorem 3.32 (Composite moduli kill the factorial). Let $n > 4$ be composite. Then

(n - 1)! \equiv 0 (mod n) .

Proof. Since $n$ is composite, write $n = ab$ with $1 < a \leq b < n$ . Two cases.

Case 1: $a < b$ . Then $a$ and $b$ are two distinct integers, both lying in ${2, 3, \dots, n - 1}$ , so both occur as separate factors in the product $(n - 1)! = 1 \cdot 2 \dots (n - 1)$ . Hence $ab = n$ divides $(n - 1)!$ .

Case 2: $a = b$ , so $n = a^{2}$ with $a \geq 2$ . If $a = 2$ then $n = 4$ , excluded by hypothesis, so $a \geq 3$ . Then

2 a < a \cdot a = n,

because $a > 2$ . So $a$ and $2 a$ are two distinct integers in the range ${2, \dots, n - 1}$ , and both appear as factors of $(n - 1)!$ . Their product $2 a^{2} = 2 n$ therefore divides $(n - 1)!$ , and in particular $n ∣ (n - 1)!$ .

In both cases $(n - 1)! \equiv 0 (mod n)$ .∎

Remark. The hypothesis $n > 4$ is used only in Case 2, and only to get $a \geq 3$ . At $n = 4$ the argument breaks exactly where the arithmetic does: $a = 2$ and $2 a = 4 = n$ is not below $n$ , so the second copy of the factor $2$ is unavailable, and indeed $3! = 6 \equiv 2 (mod 4)$ .

Corollary 3.33 (Wilson's theorem, both directions). For $n > 1$ , $(n - 1)! \equiv - 1 (mod n)$ if and only if $n$ is prime.

Proof. ( $\Rightarrow$ ) Suppose $(n - 1)! \equiv - 1 (mod n)$ and $n$ were composite. If $n > 4$ , the theorem Composite moduli kill the factorial gives $(n - 1)! \equiv 0$ , so $0 \equiv - 1 (mod n)$ , i.e. $n ∣ 1$ , impossible for $n > 1$ . The only composite $n \leq 4$ is $n = 4$ , where $3! = 6 \equiv 2 \neq \equiv - 1 \equiv 3 (mod 4)$ . So $n$ is prime.

( $\Leftarrow$ ) This is the theorem Prime implies Wilson's congruence.∎

Corollary 3.34 (A primality criterion). The function

n \mapsto g cd ((n - 1)! mod n, n)

distinguishes primes from composites for $n > 4$ : it equals $1$ when $n$ is prime and $n$ when $n$ is composite.

Proof. If $n$ is prime then $(n - 1)! \equiv - 1 \equiv n - 1 (mod n)$ and $g cd (n - 1, n) = 1$ , since any common divisor divides their difference $1$ . If $n > 4$ is composite then $(n - 1)! mod n = 0$ by the theorem Composite moduli kill the factorial, and $g cd (0, n) = n$ .∎

Pitfall. Wilson's criterion is a perfect primality test and a useless one. Computing $(n - 1)! mod n$ takes about $n$ multiplications, which is exponential in the number of digits of $n$ — far worse than trial division to $n$ . Its value is theoretical: it is the statement that primality is detectable by a single congruence, with no exceptional composites.

Example 3.35 (Composite cases in detail). Verify the theorem Composite moduli kill the factorial for $n = 12$ and for $n = 9$ , identifying the factors the proof uses.

Solution.

$n = 12 = 3 \cdot 4$ with $3 \neq = 4$ , so Case 1 applies: the factors $3$ and $4$ both appear in $11!$ , hence $12 ∣ 11!$ .
Indeed $11! = 39916800 = 12 \cdot 3326400$ , so $11! \equiv 0 (mod 12)$ .
$n = 9 = 3^{2}$ , so Case 2 applies with $a = 3$ : the factors $3$ and $6 = 2 a$ both appear in $8!$ and $3 \cdot 6 = 18$ is a multiple of $9$ .
Indeed $8! = 40320 = 9 \cdot 4480$ , so $8! \equiv 0 (mod 9)$ .

□

Exercises for §3.7 →

3.8Relations to Fermat, Euler and Quadratic Residues

Wilson's theorem is not an isolated curiosity. Combined with Fermat's little theorem it produces the criterion that governs the whole second half of this chapter, and it produces, out of nowhere, an explicit square root of $- 1$ modulo any prime $p \equiv 1 (mod 4)$ .

Definition 3.36 (Quadratic residue). Let $p$ be an odd prime and $p ∤ a$ . Then $a$ is a quadratic residue modulo $p$ if the congruence $x^{2} \equiv a (mod p)$ has a solution, and a quadratic non-residue otherwise.

Proposition 3.37 (Exactly half the residues are squares). For an odd prime $p$ , exactly $(p - 1) /2$ of the residues $1, 2, \dots, p - 1$ are quadratic residues modulo $p$ .

Proof. Consider the squaring map $σ : (Z / p Z)^{*} \to (Z / p Z)^{*}$ , $σ (x) = x^{2}$ . Its image is exactly the set of quadratic residues. For $x, y$ nonzero, $x^{2} \equiv y^{2}$ means $p ∣ (x - y) (x + y)$ , hence $y \equiv \pm x$ by Euclid's lemma. Since $p$ is odd, $x \neq \equiv - x$ (that would force $p ∣ 2 x$ ), so each fibre $σ^{- 1} (σ (x)) = {x, - x}$ has exactly two elements. A map from a set of size $p - 1$ all of whose fibres have size $2$ has image of size $(p - 1) /2$ .∎

Theorem 3.38 (Euler's criterion). Let $p$ be an odd prime and $p ∤ a$ . Then

a^{(p - 1) /2} \equiv {1 (mod p) - 1 (mod p) if a is a quadratic residue mod p, if a is a non-residue.

Proof. Put $t = a^{(p - 1) /2}$ . By Fermat's little theorem $t^{2} = a^{p - 1} \equiv 1 (mod p)$ , so by the lemma Self-inverse residues modulo a prime, $t \equiv 1$ or $t \equiv - 1$ , and these are distinct because $p$ is odd. So the only question is which.

Residues give $+ 1$ . If $a \equiv b^{2}$ with $p ∤ b$ , then $t = (b^{2})^{(p - 1) /2} = b^{p - 1} \equiv 1 (mod p)$ by Fermat's little theorem.

Nothing else gives $+ 1$ . The polynomial $X^{(p - 1) /2} - 1$ has degree $(p - 1) /2$ over the field $Z / p Z$ , so it has at most $(p - 1) /2$ roots there — a nonzero polynomial over a field has at most $de g$ many roots, as proved in Polynomial Rings and Unique Factorization. By the previous paragraph every one of the $(p - 1) /2$ quadratic residues is a root, and by the proposition Exactly half the residues are squares there are exactly that many of them. So the residues exhaust the roots, and every non-residue $a$ has $a^{(p - 1) /2} \neq \equiv 1$ , hence $\equiv - 1$ .∎

Corollary 3.39 (Wilson produces a square root of $- 1$ ). Let $p \equiv 1 (mod 4)$ be prime and set $m = \frac{p - 1}{2}$ . Then

(m!)^{2} \equiv - 1 (mod p),

so $m!$ is an explicit square root of $- 1$ modulo $p$ .

Proof. Group the factors of $(p - 1)!$ in pairs $k$ and $p - k$ for $k = 1, \dots, m$ :

(p - 1)! = k = 1 \prod m k (p - k) \equiv k = 1 \prod m k (- k) = (- 1)^{m} (k = 1 \prod m k)^{2} = (- 1)^{m} (m!)^{2} (mod p) .

By the theorem Prime implies Wilson's congruence the left side is $\equiv - 1$ . Since $p \equiv 1 (mod 4)$ , $m = (p - 1) /2$ is even, so $(- 1)^{m} = 1$ and we get $(m!)^{2} \equiv - 1 (mod p)$ .∎

Remark. For $p \equiv 3 (mod 4)$ the same computation gives $(m!)^{2} \equiv 1 (mod p)$ , so $m! \equiv \pm 1$ — no square root of $- 1$ appears, and by the corollary about to be proved in the section on supplementary laws, none can: $- 1$ is a non-residue there. Wilson's theorem therefore knows the first supplementary law already.

Example 3.40 (An explicit square root of $- 1$ ). Find a square root of $- 1$ modulo $13$ using the corollary Wilson produces a square root of $- 1$ , and check it.

Solution.

$13 \equiv 1 (mod 4)$ , so the corollary applies with $m = 6$ .
$6! = 720$ . Reduce: $720 = 55 \cdot 13 + 5$ , so $6! \equiv 5 (mod 13)$ .
Check: $5^{2} = 25 = 2 \cdot 13 - 1 \equiv - 1 (mod 13)$ . Correct.
The other square root is $- 5 \equiv 8$ , and indeed $8^{2} = 64 = 5 \cdot 13 - 1 \equiv - 1$ .

□

Exercises for §3.8 →

3.9Quadratic Reciprocity: The Statement

Euler's criterion turns the yes/no question "is $a$ a square mod $p$ ? " into a $\pm 1$ -valued computation. Naming that value makes the answer multiplicative, and multiplicativity is what makes a fast algorithm possible.

Definition 3.41 (Legendre symbol). Let $p$ be an odd prime. For an integer $a$ define

(\frac{a}{p}) = ⎩ ⎨ ⎧ 0 + 1 - 1 if p ∣ a, if a is a quadratic residue mod p, if a is a non-residue mod p .

Proposition 3.42 (Basic properties of the Legendre symbol). Let $p$ be an odd prime and $a, b$ integers. Then

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p), (\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p}), a \equiv b (mod p) \Rightarrow (\frac{a}{p}) = (\frac{b}{p}) .

Proof. The first is exactly Euler's criterion when $p ∤ a$ , and both sides are $0$ when $p ∣ a$ .

For multiplicativity, if $p$ divides $a$ or $b$ both sides are $0$ . Otherwise, by the first property,

(\frac{ab}{p}) \equiv (ab)^{(p - 1) /2} = a^{(p - 1) /2} b^{(p - 1) /2} \equiv (\frac{a}{p}) (\frac{b}{p}) (mod p) .

Both sides are $\pm 1$ , so their difference is $0$ , $2$ or $- 2$ ; it is divisible by the odd prime $p \geq 3$ , hence it is $0$ and the two sides are equal as integers.

The third property holds because whether $x^{2} \equiv a$ is solvable depends only on the class of $a$ modulo $p$ .∎

Remark. Multiplicativity says non-residues behave like $- 1$ : residue times residue is a residue, non-residue times non-residue is a residue, and residue times non-residue is a non-residue. The last is a small surprise the first time one meets it — the non-residues are not closed under multiplication.

Theorem 3.43 (Quadratic reciprocity, with both supplements). Let $p$ and $q$ be distinct odd primes. Then

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}},

and the two supplementary laws hold:

(\frac{- 1}{p}) = (- 1)^{\frac{p - 1}{2}} = {+ 1 - 1 p \equiv 1 (mod 4) p \equiv 3 (mod 4), (\frac{2}{p}) = (- 1)^{\frac{p ^{2} - 1}{8}} = {+ 1 - 1 p \equiv \pm 1 (mod 8) p \equiv \pm 3 (mod 8) .

The supplements are proved in the next section and the main law in the section Proving Reciprocity. Read the exponent $\frac{p - 1}{2} \cdot \frac{q - 1}{2}$ concretely: it is odd exactly when both $p$ and $q$ are $\equiv 3 (mod 4)$ . So the law says

(\frac{p}{q}) = ⎩ ⎨ ⎧ - (\frac{q}{p}) (\frac{q}{p}) if p \equiv q \equiv 3 (mod 4), otherwise.

Intuition. Two questions that look unrelated — is $q$ a square mod $p$ ? is $p$ a square mod $q$ ? — have the same answer, unless both primes are of the awkward type $3 mod 4$ , in which case the answers are opposite. There is no elementary reason to expect the two questions to be connected at all, which is why the theorem was conjectured by Euler, and why Gauss returned to it eight times.

Example 3.44 (Flipping a symbol). Evaluate $(\frac{7}{11})$ and $(\frac{11}{7})$ and check the law.

Solution.

Both $7$ and $11$ are $\equiv 3 (mod 4)$ , so the law predicts $(\frac{7}{11}) = - (\frac{11}{7})$ .
Compute $(\frac{11}{7}) = (\frac{4}{7}) = (\frac{2}{7})^{2} = 1$ , since $11 \equiv 4$ and $4 = 2^{2}$ is a square.
So the law predicts $(\frac{7}{11}) = - 1$ .
Check by listing squares mod $11$ : $1, 4, 9, 5, 3$ — and $7$ is not among them, so $(\frac{7}{11}) = - 1$ . The law holds.

□

Exercises for §3.9 →

3.10The Supplementary Laws and Gauss's Lemma

The first supplement is one line from Euler's criterion. The second is not, because $2$ is not a residue class we can reduce away, and it needs the sharper tool that will also carry the main theorem.

Theorem 3.45 (First supplementary law). For an odd prime $p$ ,

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2},

so $- 1$ is a quadratic residue modulo $p$ exactly when $p \equiv 1 (mod 4)$ .

Proof. By the proposition Basic properties of the Legendre symbol, $(\frac{- 1}{p}) \equiv (- 1)^{(p - 1) /2} (mod p)$ . Both sides are $\pm 1$ and differ by $0$ or $\pm 2$ ; since $p \geq 3$ is odd and divides the difference, the difference is $0$ and the two are equal.

For the restatement: $(p - 1) /2$ is even exactly when $p \equiv 1 (mod 4)$ and odd exactly when $p \equiv 3 (mod 4)$ .∎

Remark. This matches the corollary Wilson produces a square root of $- 1$ exactly, and the two proofs are independent: Wilson's construction gives the square root $(\frac{p - 1}{2})!$ when $p \equiv 1 (mod 4)$ , and Euler's criterion certifies that none exists when $p \equiv 3 (mod 4)$ .

Lemma 3.46 (Gauss's lemma). Let $p$ be an odd prime, $p ∤ a$ , and put $m = \frac{p - 1}{2}$ . For $i = 1, \dots, m$ let $r_{i} \in {1, \dots, p - 1}$ be the least positive residue of $ia$ modulo $p$ , and let

μ = # {i \in {1, \dots, m} : r_{i} > \frac{p}{2}} .

Then

(\frac{a}{p}) = (- 1)^{μ} .

Proof. Define, for each $i$ ,

s_{i} = {r_{i} p - r_{i} if r_{i} < p /2, if r_{i} > p /2.

(No $r_{i}$ equals $p /2$ , which is not an integer.) In both cases $1 \leq s_{i} \leq m$ .

The $s_{i}$ are pairwise distinct. Suppose $s_{i} = s_{j}$ . Then $r_{i} \equiv \pm r_{j} (mod p)$ , that is $ia \equiv \pm ja (mod p)$ . Cancelling the invertible $a$ gives $i \equiv \pm j (mod p)$ . The case $i \equiv - j$ is impossible: $2 \leq i + j \leq 2 m = p - 1$ , so $p ∤ i + j$ . Hence $i \equiv j (mod p)$ , and as $1 \leq i, j \leq m < p$ , $i = j$ .

So $s_{1}, \dots, s_{m}$ are $m$ distinct elements of ${1, \dots, m}$ , hence a permutation of it, and

i = 1 \prod m s_{i} = m! .

On the other hand $s_{i} \equiv \pm r_{i} (mod p)$ , with the minus sign taken exactly for the $μ$ indices where $r_{i} > p /2$ . Therefore

m! = i = 1 \prod m s_{i} \equiv (- 1)^{μ} i = 1 \prod m r_{i} \equiv (- 1)^{μ} i = 1 \prod m (ia) = (- 1)^{μ} a^{m} m! (mod p) .

Since $m!$ is a product of integers less than $p$ , it is invertible modulo $p$ and may be cancelled:

1 \equiv (- 1)^{μ} a^{m} (mod p), so a^{(p - 1) /2} = a^{m} \equiv (- 1)^{μ} (mod p) .

By Euler's criterion the left side is $(\frac{a}{p})$ , and both sides are $\pm 1$ differing by a multiple of the odd prime $p$ , so they are equal as integers.∎

Intuition. Gauss's lemma counts how many times multiplication by $a$ pushes a residue from the bottom half of ${1, \dots, p - 1}$ into the top half. Each such crossing costs a sign. The character $(\frac{a}{p})$ is nothing but the parity of the number of crossings.

Theorem 3.47 (Second supplementary law). For an odd prime $p$ ,

(\frac{2}{p}) = (- 1)^{\frac{p ^{2} - 1}{8}},

so $2$ is a quadratic residue modulo $p$ exactly when $p \equiv \pm 1 (mod 8)$ .

Proof. Apply Gauss's lemma with $a = 2$ and $m = (p - 1) /2$ . For $1 \leq i \leq m$ we have $2 \leq 2 i \leq p - 1 < p$ , so the least positive residue of $2 i$ is $2 i$ itself: $r_{i} = 2 i$ . Hence

μ = # {i \leq m : 2 i > p /2} = # {i : p /4 < i \leq m} = m - ⌊ p /4 ⌋ .

Now run the four odd residue classes modulo $8$ , writing $p = 8 k + c$ .

$c = 1$ : $m = 4 k$ , $⌊ p /4 ⌋ = 2 k$ , so $μ = 2 k$ , even.
$c = 3$ : $m = 4 k + 1$ , $⌊ p /4 ⌋ = 2 k$ , so $μ = 2 k + 1$ , odd.
$c = 5$ : $m = 4 k + 2$ , $⌊ p /4 ⌋ = 2 k + 1$ , so $μ = 2 k + 1$ , odd.
$c = 7$ : $m = 4 k + 3$ , $⌊ p /4 ⌋ = 2 k + 1$ , so $μ = 2 k + 2$ , even.

So $(- 1)^{μ} = + 1$ for $p \equiv 1, 7 (mod 8)$ and $- 1$ for $p \equiv 3, 5 (mod 8)$ , which is the stated case split since $7 \equiv - 1$ and $5 \equiv - 3$ .

Finally $(- 1)^{(p^{2} - 1) /8}$ has the same four values: writing $p = 8 k + c$ gives $\frac{p ^{2} - 1}{8} = 8 k^{2} + 2 k c + \frac{c ^{2} - 1}{8}$ , whose parity is that of $\frac{c ^{2} - 1}{8}$ , equal to $0, 1, 3, 6$ for $c = 1, 3, 5, 7$ — even, odd, odd, even.∎

Example 3.48 (Gauss's lemma computed). Use Gauss's lemma to evaluate $(\frac{3}{11})$ .

Solution.

Here $p = 11$ , $m = 5$ , $a = 3$ . The multiples are $3, 6, 9, 12, 15$ .
Least positive residues mod $11$ : $3, 6, 9, 1, 4$ .
Those exceeding $11/2 = 5.5$ are $6$ and $9$ , so $μ = 2$ .
Hence $(\frac{3}{11}) = (- 1)^{2} = 1$ : $3$ is a quadratic residue mod $11$ . Check: $5^{2} = 25 \equiv 3 (mod 11)$ .

□

Exercises for §3.10 →

3.11Evaluating Legendre Symbols Fast

Reciprocity is not only beautiful; it is an algorithm. Euler's criterion evaluates $(\frac{a}{p})$ in about $lo g p$ modular multiplications, but reciprocity does it in about $lo g p$ divisions, with no arithmetic larger than the inputs, and it is the method to use by hand.

Method 3.49 (Evaluating $(\frac{a}{p})$ by reciprocity).

Reduce the top modulo the bottom, choosing the representative in ${0, 1, \dots, p - 1}$ . If it is $0$ , the symbol is $0$ and you are done.
Factor out all powers of $2$ : each factor $2$ contributes $(\frac{2}{p}) = \pm 1$ by the second supplementary law, read off $p mod 8$ .
What remains is a product of odd primes $q$ . For each, flip $(\frac{q}{p})$ to $(\frac{p}{q})$ , inserting a sign $- 1$ exactly when $p \equiv q \equiv 3 (mod 4)$ .
Repeat from step 1 on each smaller symbol. The bottom strictly decreases at every flip, so the process ends at a symbol with top $1$ , whose value is $1$ .

Proposition 3.50 (The algorithm terminates). Each pass of the recipe Evaluating $(\frac{a}{p})$ by reciprocity strictly decreases the modulus, so the procedure halts after finitely many steps.

Proof. After step 1 the top $a^{'}$ satisfies $0 \leq a^{'} < p$ . Any odd prime $q$ appearing in its factorisation satisfies $q \leq a^{'} < p$ . Step 3 replaces the symbol $(\frac{q}{p})$ with $\pm (\frac{p}{q})$ , whose modulus is $q < p$ . A strictly decreasing sequence of positive integers is finite, and the descent stops only when no odd prime remains on top, i.e. the top is $1$ or a power of $2$ , both of which are evaluated outright.∎

Example 3.51 (A first evaluation). Compute $(\frac{219}{383})$ , given that $383$ is prime.

Solution.

$219 < 383$ , and $219 = 3 \cdot 73$ , so $(\frac{219}{383}) = (\frac{3}{383}) (\frac{73}{383})$ .
$383 = 4 \cdot 95 + 3 \equiv 3 (mod 4)$ and $3 \equiv 3 (mod 4)$ , so the flip costs a sign: $(\frac{3}{383}) = - (\frac{383}{3}) = - (\frac{2}{3})$ , since $383 \equiv 2 (mod 3)$ .
$3 \equiv 3 (mod 8)$ , so $(\frac{2}{3}) = - 1$ and therefore $(\frac{3}{383}) = - (- 1) = + 1$ .
$73 \equiv 1 (mod 4)$ , so no sign: $(\frac{73}{383}) = (\frac{383}{73}) = (\frac{18}{73})$ , since $383 = 5 \cdot 73 + 18$ .
$18 = 2 \cdot 3^{2}$ , so $(\frac{18}{73}) = (\frac{2}{73}) (\frac{3}{73})^{2} = (\frac{2}{73})$ . As $73 \equiv 1 (mod 8)$ , this is $+ 1$ .
Multiplying, $(\frac{219}{383}) = (+ 1) (+ 1) = 1$ : $219$ is a quadratic residue modulo $383$ .

□

Example 3.52 (A negative top). Compute $(\frac{- 46}{97})$ .

Solution.

Split: $- 46 = (- 1) \cdot 2 \cdot 23$ , so $(\frac{- 46}{97}) = (\frac{- 1}{97}) (\frac{2}{97}) (\frac{23}{97})$ .
$97 \equiv 1 (mod 4)$ , so $(\frac{- 1}{97}) = 1$ ; and $97 \equiv 1 (mod 8)$ , so $(\frac{2}{97}) = 1$ .
$97 \equiv 1 (mod 4)$ , so $(\frac{23}{97}) = (\frac{97}{23}) = (\frac{5}{23})$ , since $97 = 4 \cdot 23 + 5$ .
$5 \equiv 1 (mod 4)$ , so $(\frac{5}{23}) = (\frac{23}{5}) = (\frac{3}{5})$ .
$5 \equiv 1 (mod 4)$ , so $(\frac{3}{5}) = (\frac{5}{3}) = (\frac{2}{3}) = - 1$ , using $3 \equiv 3 (mod 8)$ .
Hence $(\frac{- 46}{97}) = 1 \cdot 1 \cdot (- 1) = - 1$ : the congruence $x^{2} \equiv - 46 (mod 97)$ has no solution.

□

Pitfall. Reciprocity flips only between odd primes. Before flipping you must pull out the sign and every factor of $2$ , and you must factor the top into primes — the naive flip $(\frac{15}{p}) \to \pm (\frac{p}{15})$ is meaningless, because $15$ is not prime and the Legendre symbol is defined only for a prime bottom. (The Jacobi symbol repairs this and lets the algorithm run without factoring, at the cost that $+ 1$ no longer certifies a square.)

Exercises for §3.11 →

3.12Quadratic Gauss Sums: Definition and Magnitude

The Legendre symbol is a function on residues taking values $\pm 1$ . Weighting the $p$ -th roots of unity by it produces a single complex number that encodes the whole symbol, and whose square turns out to be $\pm p$ — the arithmetic of reciprocity written as an identity between complex numbers.

Definition 3.53 (Quadratic Gauss sum). Let $p$ be an odd prime and $ζ = e^{2 πi / p}$ . The quadratic Gauss sum attached to $p$ is

g_{p} = t = 0 \sum p - 1 (\frac{t}{p}) ζ^{t} = t = 1 \sum p - 1 (\frac{t}{p}) ζ^{t},

the $t = 0$ term vanishing because $(\frac{0}{p}) = 0$ .

Proposition 3.54 (The symbol sums to zero). For an odd prime $p$ ,

t = 0 \sum p - 1 (\frac{t}{p}) = 0.

Proof. By the proposition Exactly half the residues are squares, among $t = 1, \dots, p - 1$ exactly $(p - 1) /2$ values give $+ 1$ and the remaining $(p - 1) /2$ give $- 1$ . Their sum is $0$ , and the $t = 0$ term is $0$ .∎

Lemma 3.55 (Ramanujan-style root-of-unity sum). Let $ζ = e^{2 πi / p}$ and let $c$ be an integer. Then

t = 1 \sum p - 1 ζ^{c t} = {p - 1 - 1 if p ∣ c, otherwise.

Proof. If $p ∣ c$ then $ζ^{c t} = 1$ for every $t$ and the sum has $p - 1$ terms equal to $1$ . Otherwise $ζ^{c} \neq = 1$ is a $p$ -th root of unity, so it is a root of $X^{p} - 1 = (X - 1) (X^{p - 1} + \dots + X + 1)$ , and since $ζ^{c} \neq = 1$ it is a root of the second factor. That says $\sum_{t = 0}^{p - 1} ζ^{c t} = 0$ , and subtracting the $t = 0$ term gives $- 1$ .∎

Theorem 3.56 (The Gauss sum has absolute value $p$ ). For every odd prime $p$ ,

∣ g_{p} ∣^{2} = p, so ∣ g_{p} ∣ = p .

Proof. Since $\overline{ζ^{t}} = ζ^{- t}$ and the Legendre symbol is real,

∣ g_{p} ∣^{2} = g_{p} \overline{g_{p}} = s = 1 \sum p - 1 t = 1 \sum p - 1 (\frac{s}{p}) (\frac{t}{p}) ζ^{s - t} .

For each fixed $t \in {1, \dots, p - 1}$ the map $u \mapsto s = t u$ is a bijection of ${1, \dots, p - 1}$ modulo $p$ , by the argument already used in the proof of Fermat's little theorem. Substituting $s = t u$ and using multiplicativity from the proposition Basic properties of the Legendre symbol,

(\frac{s}{p}) (\frac{t}{p}) = (\frac{t u}{p}) (\frac{t}{p}) = (\frac{u}{p}) (\frac{t}{p})^{2} = (\frac{u}{p}),

since $(\frac{t}{p})^{2} = 1$ , while $s - t = t (u - 1)$ . Therefore

∣ g_{p} ∣^{2} = u = 1 \sum p - 1 (\frac{u}{p}) t = 1 \sum p - 1 ζ^{t (u - 1)} .

By the lemma Ramanujan-style root-of-unity sum the inner sum is $p - 1$ when $u = 1$ and $- 1$ otherwise. Splitting off $u = 1$ , where $(\frac{1}{p}) = 1$ ,

∣ g_{p} ∣^{2} = (p - 1) - u = 2 \sum p - 1 (\frac{u}{p}) = (p - 1) - (0 - 1) = p,

using the proposition The symbol sums to zero for the total $\sum_{u = 1}^{p - 1} (\frac{u}{p}) = 0$ .∎

Example 3.57 (The Gauss sum for $p = 3$ ). Compute $g_{3}$ explicitly and check its magnitude.

Solution.

Modulo $3$ the squares are ${1}$ , so $(\frac{1}{3}) = 1$ and $(\frac{2}{3}) = - 1$ .
With $ζ = e^{2 πi /3}$ , $g_{3} = ζ - ζ^{2}$ .
Writing $ζ = - \frac{1}{2} + \frac{3}{2} i$ and $ζ^{2} = \overline{ζ}$ , we get $g_{3} = 3 i$ .
So $∣ g_{3} ∣ = 3$ , as the theorem The Gauss sum has absolute value $p$ requires, and $g_{3}^{2} = - 3 = (- 1)^{(3 - 1) /2} \cdot 3$ .

□

Exercises for §3.12 →

3.13The Square, and the Sign

Knowing $∣ g_{p} ∣$ leaves the argument of $g_{p}$ undetermined. The square is elementary; the sign is not, and the gap between the two is one of the famous stories in the subject.

Theorem 3.58 (The square of the Gauss sum). For every odd prime $p$ ,

g_{p}^{2} = (\frac{- 1}{p}) p = (- 1)^{(p - 1) /2} p .

In particular $g_{p}^{2} = p$ when $p \equiv 1 (mod 4)$ and $g_{p}^{2} = - p$ when $p \equiv 3 (mod 4)$ .

Proof. Conjugating term by term and then substituting $t \mapsto - t$ , which permutes the nonzero residues modulo $p$ ,

\overline{g_{p}} = t = 1 \sum p - 1 (\frac{t}{p}) ζ^{- t} = t = 1 \sum p - 1 (\frac{- t}{p}) ζ^{t} = (\frac{- 1}{p}) t = 1 \sum p - 1 (\frac{t}{p}) ζ^{t} = (\frac{- 1}{p}) g_{p},

using multiplicativity of the symbol. Multiplying by $g_{p}$ and applying the theorem The Gauss sum has absolute value $p$ ,

p = ∣ g_{p} ∣^{2} = g_{p} \overline{g_{p}} = (\frac{- 1}{p}) g_{p}^{2} .

Since $(\frac{- 1}{p}) = \pm 1$ is its own reciprocal, $g_{p}^{2} = (\frac{- 1}{p}) p$ , and the first supplementary law identifies that symbol as $(- 1)^{(p - 1) /2}$ .∎

Theorem 3.59 (Gauss's sign determination, quoted). With $ζ = e^{2 πi / p}$ ,

g_{p} = {p i p if p \equiv 1 (mod 4), if p \equiv 3 (mod 4) .

Remark. This theorem is quoted, not proved here. The theorem The square of the Gauss sum pins $g_{p}$ down to one of two values, $\pm p$ or $\pm i p$ , and no purely algebraic manipulation of the definition distinguishes them: every identity used above is invariant under the substitution $ζ \mapsto ζ^{k}$ for a quadratic residue $k$ , which is exactly the symmetry that would have to be broken. Gauss reported that the sign resisted him for four years. All known proofs use something analytic or topological — a limiting argument on theta functions, a contour integral, or a clever telescoping product — and none is elementary enough to belong here.

Example 3.60 (Confirming the sign for $p = 5$ ). Check the theorem Gauss's sign determination, quoted numerically for $p = 5$ .

Solution.

The squares mod $5$ are $1$ and $4$ , so $(\frac{1}{5}) = (\frac{4}{5}) = 1$ and $(\frac{2}{5}) = (\frac{3}{5}) = - 1$ .
With $ζ = e^{2 πi /5}$ , $g_{5} = ζ + ζ^{4} - ζ^{2} - ζ^{3} = 2 cos (2 π /5) - 2 cos (4 π /5)$ .
Numerically $2 cos 7 2^{\circ} \approx 0.6180$ and $2 cos 14 4^{\circ} \approx - 1.6180$ , so $g_{5} \approx 0.6180 + 1.6180 = 2.2360$ .
And $5 \approx 2.2360$ . Since $5 \equiv 1 (mod 4)$ , the quoted theorem predicts exactly $+ 5$ , confirmed. Note $g_{5}$ came out real and positive — the content of the theorem is that the sign is never the other one.

□

Exercises for §3.13 →

3.14Proving Reciprocity

We now prove the main law. The route is Eisenstein's: convert Gauss's lemma from a count of crossings into a count of lattice points, then observe that two such counts fill one rectangle between them.

Lemma 3.61 (Eisenstein's form of Gauss's lemma). Let $p$ be an odd prime, $m = \frac{p - 1}{2}$ , and let $a$ be an odd integer with $p ∤ a$ . Then

(\frac{a}{p}) = (- 1)^{T}, T = i = 1 \sum m ⌊ \frac{ia}{p} ⌋ .

Proof. Keep the notation of Gauss's lemma: $r_{i}$ is the least positive residue of $ia$ , and $μ$ counts the $i$ with $r_{i} > p /2$ . Division with remainder gives

ia = p ⌊ \frac{ia}{p} ⌋ + r_{i}, so a i = 1 \sum m i = pT + i = 1 \sum m r_{i} .

Write $S = \sum_{i = 1}^{m} i$ . In the proof of Gauss's lemma the numbers $s_{i}$ (equal to $r_{i}$ when $r_{i} < p /2$ and to $p - r_{i}$ otherwise) were shown to be a permutation of $1, \dots, m$ , so $\sum_{i} s_{i} = S$ . Splitting that sum by which case applies,

S = i \sum s_{i} = μ p + i \sum r_{i} - 2 r_{i} > p /2 \sum r_{i},

because each of the $μ$ large terms contributes $p - r_{i}$ in place of $r_{i}$ . Subtracting this from the previous display,

(a - 1) S = pT - μ p + 2 r_{i} > p /2 \sum r_{i} = p (T - μ) + 2 r_{i} > p /2 \sum r_{i} .

Now reduce modulo $2$ . The left side is even because $a$ is odd, and the last term is even, so $p (T - μ)$ is even; $p$ is odd, hence $T \equiv μ (mod 2)$ . Therefore $(- 1)^{T} = (- 1)^{μ} = (\frac{a}{p})$ by Gauss's lemma.∎

Lemma 3.62 (The lattice-point count). Let $p \neq = q$ be odd primes. Then

i = 1 \sum (p - 1) /2 ⌊ \frac{i q}{p} ⌋ + j = 1 \sum (q - 1) /2 ⌊ \frac{j p}{q} ⌋ = \frac{p - 1}{2} \cdot \frac{q - 1}{2} .

Proof. Let $R$ be the set of lattice points $(x, y)$ with integer coordinates satisfying

1 \leq x \leq \frac{p - 1}{2}, 1 \leq y \leq \frac{q - 1}{2},

so $∣ R ∣ = \frac{p - 1}{2} \cdot \frac{q - 1}{2}$ . Split $R$ by the line $p y = q x$ .

No point of $R$ lies on the line. If $p y = q x$ then $p ∣ q x$ , and $g cd (p, q) = 1$ forces $p ∣ x$ , impossible for $1 \leq x \leq (p - 1) /2$ .

Points below the line. For a fixed $x$ , the condition $p y < q x$ says $y < q x / p$ , so the admissible $y \geq 1$ are $y = 1, \dots, ⌊ q x / p ⌋$ — and every one of them is in range, since $x \leq (p - 1) /2$ gives $q x / p < q /2$ , hence $⌊ q x / p ⌋ \leq (q - 1) /2$ . So the count below the line is $\sum_{x} ⌊ q x / p ⌋$ , the first sum.

Points above the line. By the same argument with the roles of $(p, x)$ and $(q, y)$ exchanged, the count is $\sum_{y} ⌊ p y / q ⌋$ , the second sum.

Every point of $R$ is below or above the line and in exactly one of the two groups, so the two sums add to $∣ R ∣$ .∎

Figure 3.63. Eisenstein's rectangle for

p = 7

q = 11

. The

3 \times 5

grid of lattice points is cut by the line

p y = q x

, which passes through none of them; the

8

points below it are counted by

\sum ⌊ 11 x /7 ⌋

and the

7

above by

\sum ⌊ 7 y /11 ⌋

, and

8 + 7 = 15 = \frac{p - 1}{2} \cdot \frac{q - 1}{2}

Theorem 3.64 (Quadratic reciprocity). For distinct odd primes $p$ and $q$ ,

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} .

Proof. Both $p$ and $q$ are odd and neither divides the other, so the lemma Eisenstein's form of Gauss's lemma applies in both directions:

(\frac{q}{p}) = (- 1)^{T_{1}}, T_{1} = i = 1 \sum (p - 1) /2 ⌊ \frac{i q}{p} ⌋, (\frac{p}{q}) = (- 1)^{T_{2}}, T_{2} = j = 1 \sum (q - 1) /2 ⌊ \frac{j p}{q} ⌋ .

Multiplying and applying the lemma The lattice-point count,

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{T_{1} + T_{2}} = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} .

∎

Example 3.65 (The lattice count for $p = 7$ , $q = 11$ ). Verify both Eisenstein sums and the reciprocity sign for $p = 7$ , $q = 11$ .

Solution.

$T_{1} = ⌊ 11/7 ⌋ + ⌊ 22/7 ⌋ + ⌊ 33/7 ⌋ = 1 + 3 + 4 = 8$ .
$T_{2} = ⌊ 7/11 ⌋ + ⌊ 14/11 ⌋ + ⌊ 21/11 ⌋ + ⌊ 28/11 ⌋ + ⌊ 35/11 ⌋ = 0 + 1 + 1 + 2 + 3 = 7$ .
$T_{1} + T_{2} = 15 = 3 \cdot 5 = \frac{7 - 1}{2} \cdot \frac{11 - 1}{2}$ , as the lemma The lattice-point count requires.
So $(\frac{7}{11}) (\frac{11}{7}) = (- 1)^{15} = - 1$ , agreeing with the direct computation in the example Flipping a symbol, where the two symbols came out $- 1$ and $+ 1$ .

□

Remark. A second route, given as a sketch. Reciprocity also drops out of the Gauss sum, and it is worth seeing why, though the argument below is a sketch and is not a proof as it stands. Work in the ring $Z [ζ]$ , $ζ = e^{2 πi / p}$ , and reduce modulo the prime $q$ . Then

g_{p}^{q} \equiv t \sum (\frac{t}{p})^{q} ζ^{tq} = (\frac{q}{p}) g_{p} (mod q),

the first step because $(x + y)^{q} \equiv x^{q} + y^{q}$ in characteristic $q$ , the last by substituting $t \mapsto t q^{- 1}$ . On the other hand $g_{p}^{q} = g_{p} (g_{p}^{2})^{(q - 1) /2} = g_{p} ((- 1)^{(p - 1) /2} p)^{(q - 1) /2}$ by the theorem The square of the Gauss sum, and Euler's criterion evaluates that last factor as $(\frac{( - 1 ) ^{(p - 1) /2} p}{q})$ . Cancelling $g_{p}$ and comparing gives the law.

What this sketch assumes, and what would have to be supplied to make it a proof: that $Z [ζ]$ is a ring in which reduction modulo $q$ makes sense and in which the freshman's-dream congruence is valid; that $g_{p}$ is cancellable modulo $q$ , which needs $g_{p}^{2} = \pm p$ to be invertible modulo $q$ — true since $q \neq = p$ — together with a precise statement of what "modulo $q$ " means for the ideal $q Z [ζ]$ ; and that a congruence between the integers $\pm 1$ modulo $q \geq 3$ is an equality. None of these is hard, but all of them need the algebraic number theory of cyclotomic rings, which is why the Eisenstein argument above is the one given in full.

Exercises for §3.14 →

Common Mistakes

Dropping the coprimality in Fermat's little theorem. $a^{p - 1} \equiv 1 (mod p)$ needs $p ∤ a$ ; only the universal form $a^{p} \equiv a$ is unconditional.
Reducing an exponent modulo $n$ instead of modulo $φ (n)$ . For $2^{100} mod 7$ the right reduction is $100 mod 6 = 4$ , not $100 mod 7$ .
Using Euler's exponent as if it were the order. $φ (n)$ always works, but the true order of $a$ may be a proper divisor of it, as $ord_{20} (7) = 4 < 8 = φ (20)$ .
Treating a passed Fermat test as a proof of primality. Carmichael numbers such as $561$ , $1105$ and $1729$ pass for every coprime base.
Forgetting that the Fermat test only examines coprime bases. $561$ is divisible by $3$ , so base $3$ says nothing; the test's blindness is confined to $(Z / n Z)^{*}$ .
Forgetting the exception $n = 4$ in Wilson's converse. Every composite $n > 4$ gives $(n - 1)! \equiv 0$ , but $3! \equiv 2 (mod 4)$ .
Assuming $x^{2} \equiv 1$ has only two solutions at a composite modulus. Modulo $8$ it has four, which is precisely why the Wilson pairing argument needs a prime.
Claiming non-residues are closed under multiplication. Two non-residues multiply to a residue, since $(- 1) (- 1) = + 1$ in the Legendre symbol.
Flipping a symbol whose top is composite or even. Reciprocity relates $(\frac{p}{q})$ and $(\frac{q}{p})$ for odd primes only; pull out $- 1$ and all factors of $2$ first, using the supplementary laws.
Getting the reciprocity sign backwards. The sign is $- 1$ only when $p \equiv q \equiv 3 (mod 4)$ ; in every other case the two symbols are equal.
Reading $(\frac{a}{p}) = 1$ as " $a$ has a square root you can write down". The symbol certifies existence, not a construction; finding the root is a separate algorithm (though for $p \equiv 3 (mod 4)$ the root is simply $a^{(p + 1) /4}$ ).
Assuming $∣ g_{p} ∣ = p$ settles the Gauss sum. The magnitude is elementary; the sign is the theorem Gauss's sign determination, quoted and is not proved by any manipulation of the definition.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter