Wilson's theorem

Problem: For n ≥ 2, W(n) = (n−1)! mod n

Wilson's theorem says: n is prime iff (n−1)! ≡ −1 (mod n). This page computes the residue, explains why the theorem holds, and verifies it with harness tests.

Input

We compute (n−1)! mod n exactly using modular multiplication. If the value equals n−1 (which is −1 mod n), Wilson predicts that n is prime. We also run a basic trial‑division primality cross‑check for modest n.

Output

Residue
—
Wilson verdict
—
n prime? (trial)
—
Loops executed
—

Reason Why

(⇒) If p is prime then (p−1)! ≡ −1 (mod p). In the multiplicative group (ℤ/pℤ)^×, every element a has a unique inverse a^{-1}. All elements 2,3,…,p−2 can be paired as a·a^{-1} ≡ 1 (mod p). The only self‑inverse elements are 1 and −1, so the product (p−1)! ≡ 1·(−1) ≡ −1 (mod p).
(⇐) If (n−1)! ≡ −1 (mod n) then n is prime. If n were composite, pick a proper divisor d with 1<d<n. Then d | (n−1)!, hence (n−1)! ≡ 0 (mod d). But congruence modulo n would force (n−1)! ≡ −1 (mod d), a contradiction. Thus n must be prime.
Edge cases. The theorem is stated for n ≥ 2. For n=2, we have 1!≡1≡−1 (mod 2), consistent with the claim.
Show inverse pairs (prime n only)

Check (harness)

Preloaded Checks (harness)

Each block computes (n−1)! mod n and checks Wilson's congruence. We also compare with a trial‑division primality test for small n.