gen-briefly-explain-wilson-s-theorem-and-one-common-misconceptio-7124

Briefly explain Wilson's theorem and one common misconception about it.

# Wilson's Theorem **The theorem states:** For any integer n > 1, n is prime if and only if (n-1)! ≡ -1 (mod n). In other words, if you take the factorial of one less than a number and divide it by that number, you get a remainder of -1 (or equivalently, n-1) precisely when the number is prime. **Example:** For n = 5 (prime): 4! = 24 ≡ -1 (mod 5) ✓ For n = 6 (composite): 5! = 120 ≡ 0 (mod 6) ✗ ## Common Misconception **Misconception:** Wilson's theorem is practical for testing primality. **Reality:** While theoretically elegant, Wilson's theorem is computationally useless for primality testing. Computing (n-1)! becomes astronomically expensive even for moderately sized n. For example, testing if a 100-digit number is prime would require computing a factorial with around 10^100 terms—completely infeasible. Modern primality tests like Miller-Rabin are far more efficient.