Wilson's Theorem & Primality Reference Cheat Sheet

Wilson's Theorem gives a powerful connection between factorials and prime numbers. This cheat sheet helps students recognize when a number is prime using modular arithmetic and understand why factorial congruences matter in number theory. It is especially useful for contest math, proofs, and advanced algebra topics.

The reference focuses on formulas, conditions, and careful reasoning rather than long computations.

The central result is that an integer $p > 1$ is prime exactly when $(p - 1)! \equiv -1 \pmod{p}$ . Students also need modular inverses, congruence notation, and efficient ways to detect composites before applying a factorial test. Wilson's Theorem is elegant but not always computationally efficient for large numbers.

The most important skill is knowing when the theorem proves primality and when simpler divisibility tests should be used first.

Key Facts

Wilson's Theorem states that an integer $p > 1$ is prime if and only if $(p - 1)! \equiv -1 \pmod{p}$ .
The congruence $(p - 1)! \equiv -1 \pmod{p}$ is equivalent to $(p - 1)! \equiv p - 1 \pmod{p}$ .
If $n > 1$ and $(n - 1)! \not\equiv -1 \pmod{n}$ , then $n$ is composite.
To test whether $n$ is prime by trial division, check divisibility only by primes $q$ with $q \leq \sqrt{n}$ .
For a prime $p$ , every nonzero residue $a$ modulo $p$ has a modular inverse $a^{-1}$ such that $a a^{-1} \equiv 1 \pmod{p}$ .
In the proof of Wilson's Theorem, most residues modulo a prime pair with their inverses, leaving only $1$ and $p - 1$ because $x^2 \equiv 1 \pmod{p}$ has solutions $x \equiv \pm 1 \pmod{p}$ .
For a prime $p$ , Wilson's Theorem can be rearranged as $(p - 2)! \equiv 1 \pmod{p}$ because $(p - 1)! = (p - 1)(p - 2)!$ .
Wilson's Theorem is a true primality criterion, but computing $(n - 1)! \pmod{n}$ is usually inefficient for large $n$ .

Vocabulary

Prime number: A prime number is an integer greater than $1$ whose only positive divisors are $1$ and itself.
Composite number: A composite number is an integer greater than $1$ that has at least one positive divisor other than $1$ and itself.
Congruence: The statement $a \equiv b \pmod{n}$ means that $n$ divides $a - b$ .
Factorial: The factorial $n!$ is the product $n! = n(n - 1)(n - 2)\cdots 2 \cdot 1$ for positive integers $n$ .
Modular inverse: A modular inverse of $a$ modulo $n$ is a number $b$ such that $ab \equiv 1 \pmod{n}$ .
Primality test: A primality test is a method used to decide whether a given integer is prime or composite.

Common Mistakes to Avoid

Using Wilson's Theorem on $n = 1$ is wrong because the theorem requires an integer $p > 1$ and primality is only defined for integers greater than $1$ .
Forgetting the negative residue is wrong because $(p - 1)! \equiv -1 \pmod{p}$ means the same as $(p - 1)! \equiv p - 1 \pmod{p}$ , not $1$ .
Assuming Wilson's Theorem is fast for large numbers is wrong because calculating $(n - 1)! \pmod{n}$ can require many multiplications.
Checking divisibility past $\sqrt{n}$ is unnecessary because if $n = ab$ and both $a > \sqrt{n}$ and $b > \sqrt{n}$ , then $ab > n$ .
Claiming that $(n - 1)! \equiv -1 \pmod{n}$ only suggests primality is wrong because Wilson's Theorem gives an if and only if condition for $n > 1$ .

Practice Questions

1 Use Wilson's Theorem to verify that $5$ is prime by computing $4! \pmod{5}$ .
2 Determine whether $6$ passes Wilson's Theorem by computing $5! \pmod{6}$ .
3 For the prime $p = 11$ , find the value of $10! \pmod{11}$ without multiplying all factors.
4 Explain why Wilson's Theorem is useful for proving facts about primes but is usually not the best practical method for testing very large numbers.

Sign in to save

Sign in to save

Wilson's Theorem & Primality Reference Cheat Sheet

Related Tools

Related Worksheets

Related Infographics

Study as Flashcards

Key Facts

Vocabulary

Common Mistakes to Avoid

Practice Questions