Number TheoryDifficulty 45-9015 tagged problems

Wilson's Theorem

Wilson's Theorem is the habit of using factorial residues modulo primes to identify primality and simplify congruences. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$(p - 1)! \equiv -1 \pmod{p} \iff p \text{ is prime}$$

The product of all residues from $1$ to $p-1$ is congruent to $-1$ modulo $p$ precisely when $p$ is prime.

Why It Works

1
For prime $p$, every residue in $\{1, \dots, p-1\}$ has a unique inverse in that set.
2
A residue is its own inverse only when $x^2 \equiv 1 \pmod p$, i.e. $(x-1)(x+1) \equiv 0$, which gives just $x \equiv 1$ and $x \equiv p-1$.
3
All other residues pair off with distinct inverses whose product is $1$, so $(p-1)! \equiv 1 \cdot (p-1) \cdot 1 \equiv p - 1 \equiv -1 \pmod p$.
4
If $p$ is composite with a factor $1 < d < p$, then $d \mid (p-1)!$, so $(p-1)! \equiv 0 \not\equiv -1$, confirming the biconditional.

Worked Examples

Example 1

Compute $16! \bmod 17$.

1
Note $17$ is prime, and $16 = 17 - 1$, so Wilson's theorem applies directly.
2
Wilson gives $16! \equiv -1 \pmod{17}$.
3
Express $-1$ as a residue in $\{0, \dots, 16\}$: $-1 \equiv 16 \pmod{17}$.
4
Hence $16! \equiv 16 \pmod{17}$.

Answer:

$16$

Warm-up

Compute $12! \bmod 13$.

1
$13$ is prime and $12 = 13 - 1$, so Wilson's theorem applies: $(13 - 1)! \equiv -1 \pmod{13}$.
2
Thus $12! \equiv -1 \pmod{13}$.
3
Convert to a standard residue: $-1 \equiv 12 \pmod{13}$.
4
Hence $12! \equiv 12 \pmod{13}$.

Answer:

$12$

Contest level

Find the remainder when $15!$ is divided by $17$.

1
$17$ is prime, so Wilson gives $16! \equiv -1 \pmod{17}$.
2
Relate $16!$ to $15!$: $16! = 16 \cdot 15!$, and $16 \equiv -1 \pmod{17}$, so $16! \equiv -15! \pmod{17}$.
3
Combine: $-15! \equiv -1 \pmod{17}$, hence $15! \equiv 1 \pmod{17}$.
4
(This is the general fact $(p-2)! \equiv 1 \pmod p$ for prime $p$.)

Answer:

$1$

Olympiad / Challenge

Let $p$ be a prime with $p \equiv 1 \pmod 4$. Prove that $\left(\left(\tfrac{p-1}{2}\right)!\right)^2 \equiv -1 \pmod p$, so $-1$ is a quadratic residue mod $p$.

1
Start from Wilson: $(p-1)! \equiv -1 \pmod p$. Pair each factor $k$ with $p - k$ for $k = 1, \dots, \tfrac{p-1}{2}$, which uses every factor of $(p-1)!$ exactly once.
2
Modulo $p$, $p - k \equiv -k$, so $(p-1)! = \prod_{k=1}^{(p-1)/2} k\,(p-k) \equiv \prod_{k=1}^{(p-1)/2} k\,(-k) = (-1)^{(p-1)/2} \left(\left(\tfrac{p-1}{2}\right)!\right)^2 \pmod p$.
3
Since $p \equiv 1 \pmod 4$, the exponent $\tfrac{p-1}{2}$ is even, so $(-1)^{(p-1)/2} = 1$.
4
Therefore $\left(\left(\tfrac{p-1}{2}\right)!\right)^2 \equiv (p-1)! \equiv -1 \pmod p$. Setting $x = \left(\tfrac{p-1}{2}\right)!$ gives $x^2 \equiv -1$, so $-1$ is a quadratic residue. (Check $p = 5$: $(2!)^2 = 4 \equiv -1 \pmod 5$. ✓)

Answer:

$\left(\left(\tfrac{p-1}{2}\right)!\right)^2 \equiv -1 \pmod p$; $-1$ is a QR when $p \equiv 1 \pmod 4$.

Going Deeper

Generalization: Wilson is one direction of a biconditional — $(n-1)! \equiv -1 \pmod n$ holds iff $n$ is prime. For composite $n > 4$, $(n-1)! \equiv 0 \pmod n$; the lone exception is $n = 4$, where $3! = 6 \equiv 2 \pmod 4$. The self-pairing residues are exactly the solutions of $x^2 \equiv 1$, which is why the proof reduces to $1$ and $p - 1$.
Where it appears: evaluating $(p-1)!$ or near-factorials modulo a prime, proving $-1$ is a quadratic residue mod $p$ iff $p \equiv 1 \pmod 4$, constructing solutions to $x^2 \equiv -1 \pmod p$, and as a primality criterion (theoretically clean but computationally slow).
Pitfall: Wilson requires the modulus to be PRIME — $(n-1)! \equiv -1$ fails for every composite $n$ (it is $\equiv 0$, except $n = 4$). Also be careful pairing factors: a residue equal to its own inverse ($1$ and $p-1$) must not be paired with a distinct partner, or you double-count; the clean product only works once those two are set aside (or, as above, the symmetric $k \leftrightarrow p-k$ pairing is used instead).

Spot the Signal

Look for problems where the key step is using factorial residues modulo primes to identify primality and simplify congruences.
You can describe the hard part as using factorial residues modulo primes to identify primality and simplify congruences, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for wilson's theorem, then rewrite the givens around it.
Name the relation that makes Wilson's Theorem legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Wilson's Theorem just because the surface looks familiar; verify the required condition first.
Applying Wilson's Theorem because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let wilson's theorem reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using factorial residues modulo primes to identify primality and simplify congruences.

Back to techniques

Number TheoryDifficulty 45-9015 tagged problems

Wilson's Theorem

Practice this technique Match my level

The Key Result

$$(p - 1)! \equiv -1 \pmod{p} \iff p \text{ is prime}$$

The product of all residues from $1$ to $p-1$ is congruent to $-1$ modulo $p$ precisely when $p$ is prime.

Why It Works

1
For prime $p$, every residue in $\{1, \dots, p-1\}$ has a unique inverse in that set.
2
A residue is its own inverse only when $x^2 \equiv 1 \pmod p$, i.e. $(x-1)(x+1) \equiv 0$, which gives just $x \equiv 1$ and $x \equiv p-1$.
3
All other residues pair off with distinct inverses whose product is $1$, so $(p-1)! \equiv 1 \cdot (p-1) \cdot 1 \equiv p - 1 \equiv -1 \pmod p$.
4
If $p$ is composite with a factor $1 < d < p$, then $d \mid (p-1)!$, so $(p-1)! \equiv 0 \not\equiv -1$, confirming the biconditional.

Worked Examples

Example 1

Compute $16! \bmod 17$.

1
Note $17$ is prime, and $16 = 17 - 1$, so Wilson's theorem applies directly.
2
Wilson gives $16! \equiv -1 \pmod{17}$.
3
Express $-1$ as a residue in $\{0, \dots, 16\}$: $-1 \equiv 16 \pmod{17}$.
4
Hence $16! \equiv 16 \pmod{17}$.

Answer:

$16$

Warm-up

Compute $12! \bmod 13$.

1
$13$ is prime and $12 = 13 - 1$, so Wilson's theorem applies: $(13 - 1)! \equiv -1 \pmod{13}$.
2
Thus $12! \equiv -1 \pmod{13}$.
3
Convert to a standard residue: $-1 \equiv 12 \pmod{13}$.
4
Hence $12! \equiv 12 \pmod{13}$.

Answer:

$12$

Contest level

Find the remainder when $15!$ is divided by $17$.

1
$17$ is prime, so Wilson gives $16! \equiv -1 \pmod{17}$.
2
Relate $16!$ to $15!$: $16! = 16 \cdot 15!$, and $16 \equiv -1 \pmod{17}$, so $16! \equiv -15! \pmod{17}$.
3
Combine: $-15! \equiv -1 \pmod{17}$, hence $15! \equiv 1 \pmod{17}$.
4
(This is the general fact $(p-2)! \equiv 1 \pmod p$ for prime $p$.)

Answer:

$1$

Olympiad / Challenge

Let $p$ be a prime with $p \equiv 1 \pmod 4$. Prove that $\left(\left(\tfrac{p-1}{2}\right)!\right)^2 \equiv -1 \pmod p$, so $-1$ is a quadratic residue mod $p$.

1
Start from Wilson: $(p-1)! \equiv -1 \pmod p$. Pair each factor $k$ with $p - k$ for $k = 1, \dots, \tfrac{p-1}{2}$, which uses every factor of $(p-1)!$ exactly once.
2
Modulo $p$, $p - k \equiv -k$, so $(p-1)! = \prod_{k=1}^{(p-1)/2} k\,(p-k) \equiv \prod_{k=1}^{(p-1)/2} k\,(-k) = (-1)^{(p-1)/2} \left(\left(\tfrac{p-1}{2}\right)!\right)^2 \pmod p$.
3
Since $p \equiv 1 \pmod 4$, the exponent $\tfrac{p-1}{2}$ is even, so $(-1)^{(p-1)/2} = 1$.
4
Therefore $\left(\left(\tfrac{p-1}{2}\right)!\right)^2 \equiv (p-1)! \equiv -1 \pmod p$. Setting $x = \left(\tfrac{p-1}{2}\right)!$ gives $x^2 \equiv -1$, so $-1$ is a quadratic residue. (Check $p = 5$: $(2!)^2 = 4 \equiv -1 \pmod 5$. ✓)

Answer:

$\left(\left(\tfrac{p-1}{2}\right)!\right)^2 \equiv -1 \pmod p$; $-1$ is a QR when $p \equiv 1 \pmod 4$.

Going Deeper

Generalization: Wilson is one direction of a biconditional — $(n-1)! \equiv -1 \pmod n$ holds iff $n$ is prime. For composite $n > 4$, $(n-1)! \equiv 0 \pmod n$; the lone exception is $n = 4$, where $3! = 6 \equiv 2 \pmod 4$. The self-pairing residues are exactly the solutions of $x^2 \equiv 1$, which is why the proof reduces to $1$ and $p - 1$.
Where it appears: evaluating $(p-1)!$ or near-factorials modulo a prime, proving $-1$ is a quadratic residue mod $p$ iff $p \equiv 1 \pmod 4$, constructing solutions to $x^2 \equiv -1 \pmod p$, and as a primality criterion (theoretically clean but computationally slow).
Pitfall: Wilson requires the modulus to be PRIME — $(n-1)! \equiv -1$ fails for every composite $n$ (it is $\equiv 0$, except $n = 4$). Also be careful pairing factors: a residue equal to its own inverse ($1$ and $p-1$) must not be paired with a distinct partner, or you double-count; the clean product only works once those two are set aside (or, as above, the symmetric $k \leftrightarrow p-k$ pairing is used instead).

Spot the Signal

Look for problems where the key step is using factorial residues modulo primes to identify primality and simplify congruences.
You can describe the hard part as using factorial residues modulo primes to identify primality and simplify congruences, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for wilson's theorem, then rewrite the givens around it.
Name the relation that makes Wilson's Theorem legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Wilson's Theorem just because the surface looks familiar; verify the required condition first.
Applying Wilson's Theorem because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let wilson's theorem reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using factorial residues modulo primes to identify primality and simplify congruences.