You compute 10! mod 11 and get 10. Does Wilson's theorem confirm that 11 is prime?
AYes — since 10 ≡ −1 (mod 11), this satisfies Wilson's condition and confirms 11 is prime
BNo — Wilson's theorem only applies when (p−1)! ≡ 0 (mod p)
CYes — but only because 10! happened to be divisible by a factor of 11−1
DCannot determine — Wilson's theorem requires computing the result in a different form
10 ≡ −1 (mod 11) because 10 = 11 − 1. So 10! ≡ −1 (mod 11), which is exactly the condition Wilson's theorem requires. Since the congruence holds, Wilson's theorem confirms 11 is prime. Option B confuses the condition — Wilson's theorem requires (p−1)! ≡ −1 (mod p), not ≡ 0.
Question 2 Multiple Choice
For a prime p, what happens to the elements {2, 3, ..., p−2} when computing (p−1)! mod p?
AThey are each divisible by p, so they contribute 0 to the product
BThey alternate in sign, canceling each other out
CEach pairs with its distinct multiplicative inverse in the same set, contributing a factor of 1 to the product
DThey collectively produce a factor of (p−1)/2, which then cancels with the remaining terms
Every element a in {2, ..., p−2} has a multiplicative inverse mod p that is also in {2, ..., p−2} and distinct from a — the only self-inverse elements are 1 and p−1 (since a² ≡ 1 mod p implies a ≡ ±1 mod p). Each pair a · a⁻¹ ≡ 1 (mod p), so all these terms cancel to 1. What remains in the product is just 1 · (p−1) = p−1 ≡ −1 (mod p).
Question 3 True / False
Wilson's theorem provides an efficient algorithm for determining whether a large number is prime, since it gives an exact characterization of primality.
TTrue
FFalse
Answer: False
Wilson's theorem provides a theoretically exact characterization — p is prime if and only if (p−1)! ≡ −1 (mod p) — but computing (p−1)! for large p is astronomically expensive. A number with 100 digits would require computing a factorial of roughly 10^100 terms. This makes it completely impractical as a primality test. Its value is theoretical, not computational.
Question 4 True / False
In the proof of Wilson's theorem, the reason the product (p−1)! simplifies cleanly is that 1 and p−1 are the only elements in {1, ..., p−1} that are their own multiplicative inverses mod p.
TTrue
FFalse
Answer: True
An element a is self-inverse if a² ≡ 1 (mod p), i.e., p divides (a−1)(a+1). Since p is prime, p must divide a−1 or a+1, giving a ≡ 1 or a ≡ −1 ≡ p−1 (mod p). These are the only two self-inverse elements. All other elements pair with a distinct inverse, contributing 1 to the product, leaving just 1 · (p−1) ≡ −1 (mod p).
Question 5 Short Answer
Why does Wilson's theorem fail for composite numbers? Explain why (n−1)! ≢ −1 (mod n) when n is composite.
Think about your answer, then reveal below.
Model answer: When n is composite, n has a factor a with 1 < a < n. Since a ≤ n−1, a appears as one of the factors in (n−1)!, so a divides (n−1)!. If (n−1)! ≡ −1 (mod n) were true, then n would divide (n−1)! + 1, and since a divides n, a would also divide (n−1)! + 1 — yet a already divides (n−1)!, so a would divide their difference 1. This is a contradiction since a > 1.
The core issue is that composite numbers have factors smaller than themselves that appear in the factorial. The congruence (n−1)! ≡ −1 (mod n) would require n to divide (n−1)! + 1, but any nontrivial factor of n also divides (n−1)!, making it divide 1 — impossible. This is why the congruence holds only for primes.