Back to the on-screen lesson ·
The product of every non-zero residue modulo a prime is minus one, the converse holds, and the resulting primality test is unusable.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state Wilson's theorem and prove it by pairing each residue with its inverse, say why exactly two residues modulo a prime are their own inverse, state and prove the converse including the exceptional case, and explain why a criterion that characterises the primes exactly can still be worse than trial division.
Lesson 7 wrote out the units modulo $7$ and noticed the inverses pair up: $2 \leftrightarrow 4$, $3 \leftrightarrow 5$, with $1$ and $6$ their own inverses. Lesson 11 then multiplied a whole list of residues together and cancelled $(p-1)!$ as a unit.
This lesson asks what that product actually is. The answer follows from the pairing with nothing else added: the paired residues multiply to $1$ and vanish, so only the self-paired ones survive — and there are exactly two of them, for a reason that is itself worth proving.
$(n-1)!$ here always means the product $1 \cdot 2 \cdots (n-1)$ reduced modulo $n$; the factorial itself is never computed.
A residue is self-inverse (an involution) when $x \cdot x \equiv 1$, that is $x^{2} \equiv 1 \pmod n$. Modulo a prime there are exactly two; modulo $8$ there are four.
A primality criterion is a condition equivalent to being prime. Wilson's is one, in contrast to the Fermat test, which is a one-way condition: failing it proves compositeness and passing it proves nothing.
Wilson's theorem. For a prime $p$, $$(p-1)! \equiv -1 \pmod p.$$
Proof. Modulo a prime every residue $1, \ldots, p-1$ is a unit, so each has a unique inverse among them. Pair each with its inverse. A residue is paired with itself exactly when $x^2 \equiv 1$, that is when $p \mid (x-1)(x+1)$; since $p$ is prime it divides one of the factors, so $x \equiv 1$ or $x \equiv -1$, and there are no others. The remaining $p-3$ residues split into $(p-3)/2$ pairs, each contributing $1$ to the product. What is left is $1 \cdot (p-1) \equiv -1$.
Primality is used twice: to give every residue an inverse, and to stop $x^2 \equiv 1$ having extra solutions. Modulo $8$ it has four solutions and the argument collapses.
The converse. If $(n-1)! \equiv -1 \pmod n$ then $n$ is prime. For composite $n > 4$, write $n = ab$ with $1 < a \le b < n$. If $a \ne b$, both appear as distinct factors of $(n-1)!$, so $n \mid (n-1)!$ and the product is $0$. If $a = b$, then $n = a^2$ with $a > 2$, so $a$ and $2a$ are both below $n$ and both appear, again giving $0$. Either way $(n-1)! \equiv 0 \not\equiv -1$. The single exception is $n = 4$, where $3! = 6 \equiv 2$.
So the congruence holds exactly for the primes: a genuine characterisation, not a one-way test.
And it is useless. Computing $(n-1)! \bmod n$ takes $n - 2$ multiplications. Trial division takes about $\sqrt n$ divisions, and Miller–Rabin takes a few exponentiations. Wilson's criterion is exponentially worse than the crudest practical method, and it is the standing example of a theorem that is exactly right and computationally hopeless.
Another way: steps
Another way: example
$10! \bmod 11$: $11$ is prime, so the answer is $10$. $11! \bmod 12$: $12$ is composite and above $4$, so the answer is $0$ — indeed $3 \cdot 4 = 12$ appears inside the product. $9! \bmod 11$: drop the factor $10 \equiv -1$ from $10! \equiv -1$ by multiplying by its inverse, which is itself, giving $1$.
Wilson's theorem is the cleanest example in elementary number theory of a distinction worth internalising: a mathematical characterisation and a usable test are different things.
Compare the three criteria this course has met.
Trial division. $n$ is prime exactly when no prime up to $\sqrt n$ divides it. A characterisation, and a usable test for small $n$ — about $\sqrt n / \ln n$ divisions. At a hundred digits that is $10^{48}$ operations, so it is usable only up to about twenty digits.
The Fermat test. If $a^{n-1} \not\equiv 1 \pmod n$ then $n$ is composite. Not a characterisation — Carmichael numbers pass for every base — but extremely cheap, about $\log n$ multiplications. One-way, fast, and the basis of what is actually used.
Wilson's criterion. $n$ is prime exactly when $(n-1)! \equiv -1 \pmod n$. A perfect characterisation, both directions, no exceptions above $4$ — and $n$ multiplications, which is worse than trial division by a factor of $\sqrt n$. Nobody has ever used it to test anything.
The pattern generalises. The property being prime is easy to state exactly and hard to compute; the practical tests trade exactness for speed and then buy the exactness back with repetition, as Miller–Rabin does by running many bases. A criterion that quantifies over everything below $n$ — every residue, every factor — will cost about $n$ to check, and the whole art is finding conditions that do not.
Wilson's theorem is still worth having. It is used in proofs — for instance to show that $x^2 \equiv -1 \pmod p$ is solvable when $p \equiv 1 \pmod 4$, by taking $x = ((p-1)/2)!$ — and that is where its value lies.
Computing the factorial. $(n-1)!$ is never computed as an integer. It is a product reduced modulo $n$ at every step, and for the theorem's purposes it is not computed at all.
Forgetting $n = 4$. Every composite above $4$ gives $0$; $4$ gives $2$. It is the only exception and it is the one a general claim about composites always trips over.
Reading $-1$ as a negative answer. The least residue is $n - 1$. Writing the theorem with $-1$ is what makes it one statement rather than a family of them.
Assuming more residues are self-inverse. Modulo a prime there are exactly two, and that fact is a use of primality, not an observation. Modulo $8$ every unit is self-inverse.
Treating the criterion as a test. It is exact and it is exponentially slower than trial division. Knowing a criterion is correct says nothing about whether it can be run.
Modulo $13$: the residues $2, \ldots, 11$ pair as $2 \cdot 7$, $3 \cdot 9$, $4 \cdot 10$, $5 \cdot 8$, $6 \cdot 11$, each product $\equiv 1$.
Five pairs, using up the ten middle residues.
So $12! \equiv 1 \cdot 12 \equiv -1 \pmod{13}$, as the theorem promises.
Only the two self-inverse residues survive.
Modulo $14$: the factors $2$ and $7$ both appear among $1, \ldots, 13$, so $14 \mid 13!$ and $13! \equiv 0$. Composite, and the criterion says so.
The converse, in one line.
Show that $x^{2} \equiv -1 \pmod p$ is solvable when $p \equiv 1 \pmod 4$. Write $(p-1)!$ as the first half times the second half.
Split the product rather than evaluating it.
Each factor $p - k$ in the second half is $\equiv -k$, so the second half is $(-1)^{(p-1)/2}$ times the first half. With $p \equiv 1 \pmod 4$ the exponent $(p-1)/2$ is even, so that sign is $+1$.
The hypothesis on $p$ enters exactly here.
So $-1 \equiv (p-1)! \equiv \left(\left(\tfrac{p-1}{2}\right)!\right)^{2}$, and $x = ((p-1)/2)!$ is a square root of $-1$. That fact is the heart of unit 4.
A theorem about a product, used to construct a solution.
Wilson gives the full product: $16! \equiv -1 \pmod{17}$.
Start from the theorem, not from the factorial.
$15!$ is $16!$ with the last factor removed, so multiply by the inverse of $16$. Since $16 \equiv -1$, its inverse is itself.
Removing a factor is multiplying by its inverse.
So $15! \equiv (-1) \cdot (-1) = 1 \pmod{17}$.
For each modulus, give the least residue of the product of all the positive integers below it.
| Least residue of the product | |
|---|---|
| Modulo $7$ | |
| Modulo $3$ | |
| Modulo $15$ |
What is the least residue of $1 \times 2 \times \cdots \times 4$ modulo $5$?
Answer:
Is this true: $(p-1)! \equiv -1 \pmod p$ for every prime $p$?
Build the proof that $(p-1)! \equiv -1 \pmod p$ for an odd prime $p$.
This task has no paper form; do it on a device.
Match each modulus to the least residue of the product of all the positive integers below it.
| $12$ | $0$ | $16$ | |
|---|---|---|---|
| modulo $13$ | |||
| modulo $8$ | |||
| modulo $17$ |
Working modulo $13$, what is the least residue of $1 \times 2 \times \cdots \times 11$ — the product of every positive integer below $13$ except $12$?
least residue a
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For each modulus, give the least residue of the product of all the positive integers below it.
| Least residue of the product | |
|---|---|
| Modulo $23$ | |
| Modulo $13$ | |
| Modulo $20$ |
You can evaluate the product of the residues below any modulus and say what the answer tells you. Say in your own words why a correct primality criterion may be of no practical use. Next: which powers of a residue return it to one, and how soon.
9. Your turn: what is $15! \bmod 17$?, step 3