Wilson's Theorem — Definition, Formula & Examples
Wilson's Theorem says that for any prime number , the factorial leaves a remainder of when divided by . Equivalently, is divisible by , and this property holds only for primes.
An integer is prime if and only if . This provides a necessary and sufficient condition for primality, though it is computationally impractical for large numbers due to the cost of computing factorials.
Key Formula
Where:
- = A positive integer greater than 1 being tested for primality
- = The factorial of p − 1, i.e., the product 1 × 2 × 3 × ⋯ × (p−1)
How It Works
To apply Wilson's Theorem, compute and check whether dividing it by gives a remainder of (which is the same as ). If it does, is prime. If you already know is prime, you can use the theorem to simplify modular factorial expressions without computing the full factorial. For composite numbers, in most cases, because 's factors appear within the product .
Worked Example
Problem: Verify Wilson's Theorem for p = 7.
Compute (p−1)!: Calculate 6! = 1 × 2 × 3 × 4 × 5 × 6.
Divide by p: Divide 720 by 7 and find the remainder.
Check the condition: The remainder is 6, which equals p − 1 = 7 − 1. In modular terms, 6 ≡ −1 (mod 7).
Answer: Since 6! ≡ −1 (mod 7), Wilson's Theorem is confirmed and 7 is indeed prime.
Why It Matters
Wilson's Theorem is a cornerstone result in number theory that connects factorials and primes in a surprising way. It appears in math competitions (AMC, AIME, olympiads) where you need to evaluate large factorials modulo a prime, and it serves as a theoretical foundation for deeper results in abstract algebra and cryptography.
Common Mistakes
Mistake: Thinking Wilson's Theorem says (p-1)! ≡ 1 (mod p) instead of −1.
Correction: The correct congruence is (p−1)! ≡ −1 (mod p). A remainder of −1 mod p is the same as a remainder of p − 1, not 1.