Questions: Wilson's Theorem

Question 1

A student wants to test whether a 500-digit number is prime using Wilson's theorem: compute (n−1)! mod n and check if it equals −1. A classmate says this is a valid but impractical primality test. Which response best explains the computational problem?

• A. The test is invalid — Wilson's theorem only works for primes less than 100
• B. The test is valid but requires computing a factorial with ~10^500 multiplications, making it exponentially slower than methods like Miller-Rabin
• C. The test is valid and efficient because modular reduction keeps the numbers small throughout
• D. The test is invalid for even numbers, but fast for odd candidates

Answer: (B)

Wilson's theorem gives an exact characterization of primes — (n−1)! ≡ −1 (mod n) if and only if n is prime — so the test is logically valid. The problem is computational: (n−1)! requires (n−2) multiplications, and n itself is exponentially large in its bit length. A 500-digit prime has roughly 10^500 multiplications to perform, making it laughably impractical. Fermat's little test and Miller-Rabin use modular exponentiation, which is polynomial in the bit length. Option C is the key misconception: while mod reduction does keep individual numbers small, it cannot reduce the number of operations needed.

Question 2

In the proof of Wilson's theorem, why does the element p−1 not cancel with a distinct partner, and what role does this play in the final result?

• A. p−1 is even, so it has no modular inverse
• B. p−1 ≡ −1 (mod p), so (p−1)² ≡ 1 (mod p) — it is self-inverse and contributes the factor of −1 to (p−1)!
• C. p−1 cancels with 1, leaving the middle terms to contribute −1
• D. p−1 is the largest element, so it has no smaller element to pair with

Answer: (B)

The pairing argument pairs each element a in {1, ..., p−1} with its distinct multiplicative inverse a⁻¹. Most elements pair with a different element, contributing 1 to the product. The exceptions are the self-inverse elements where a ≡ a⁻¹, i.e., a² ≡ 1 (mod p). For a prime p, this equation has exactly two solutions: a ≡ 1 and a ≡ −1 ≡ p−1. So 1 and p−1 are left unpaired. Their product is 1 · (p−1) ≡ −1 (mod p), giving (p−1)! ≡ −1 (mod p).

Question 3

Wilson's theorem states that n is prime if and only if (n−1)! ≡ −1 (mod n). For composite n > 4, (n−1)! ≡ 0 (mod n) rather than −1.

• T. True
• F. False

Answer: True

For composite n > 4, n has a proper factor d with 1 < d < n. Since d appears in {1, 2, ..., n−1} and n's factors appear multiple times in that product, n divides (n−1)!. So (n−1)! ≡ 0 (mod n), not −1. This is why the theorem provides a perfect if-and-only-if characterization of primes.

Question 4

Because Wilson's theorem provides an exact test for primality, it is more reliable than probabilistic tests like Miller-Rabin, which mainly give probable primality.

• T. True
• F. False

Answer: False

While Wilson's theorem is exact (no false positives or negatives), reliability in practice is not the same as mathematical exactness. Miller-Rabin is deterministic for all practical inputs (with multiple witnesses it has no false positives in the numbers we care about) and runs in polynomial time. Wilson's test requires computing a factorial with exponentially many steps, making it computationally useless for any large prime regardless of its theoretical exactness. Practical reliability favors the probabilistic tests overwhelmingly.

Question 5

Why does the pairing argument in the proof of Wilson's theorem fail for composite numbers? What property of primes makes it work?

Model answer: For prime p, every nonzero element in ℤ/pℤ has a unique multiplicative inverse because ℤ/pℤ is a field. This means the elements of {1, ..., p−1} can be paired with their distinct inverses, each pair contributing 1 to the product, leaving only the self-inverse elements 1 and p−1 = −1. For composite n, the integers mod n do not form a field — zero divisors exist, and some elements lack inverses. The factor d of n appears in {1, ..., n−1}, and n divides the product, so (n−1)! ≡ 0 (mod n). The clean cancellation that powers the proof depends entirely on the field structure, which only exists when the modulus is prime.

The key is that primality guarantees a field structure (every nonzero element has a unique inverse), which makes the pairing argument work perfectly. Compositeness introduces zero divisors and elements without inverses, breaking the pairing and forcing the product to 0 rather than −1.