# Wilson's Theorem Primality Checker

(n−1)! ≡ −1 (mod n) ⟺ n is prime. Exact factorial residue for n ≤ 10⁷, Miller–Rabin cross-check, composite factorial law, optional running-products trace.

> Canonical page: https://elysiatools.com/en/tools/wilson-theorem-checker

- **Category:** Math & Numbers

- **Keywords:** wilson's theorem, primality test, factorial, modular arithmetic, miller-rabin, number theory, prime checker

## Overview

The Wilson's Theorem Primality Checker evaluates whether an integer n is prime by computing the factorial residue (n−1)! modulo n. It tests the classical congruence (n−1)! ≡ −1 (mod n), cross-checks the result using deterministic Miller–Rabin, evaluates the composite factorial law, and optionally outputs running modular products.

## Inputs

- **Number n** (text): 2 ≤ n ≤ 10⁷ (one factorial-modulo pass).
- **Output detail** (select)

## When to use

- Verifying primality for integers up to 10⁷ using exact Wilson's theorem modular reduction.
- Studying step-by-step modular residue sequences k! mod n for educational or number theory demonstrations.
- Demonstrating the composite factorial law where (n−1)! ≡ 0 (mod n) for composite numbers greater than 4.

## How it works

- Enter an integer n within the supported range (2 ≤ n ≤ 10⁷) and choose the desired output detail level.
- The tool iteratively multiplies k from 1 to n−1 modulo n to compute the exact residue of (n−1)! mod n.
- It checks if the residue equals n − 1 (representing −1 mod n) and applies deterministic Miller–Rabin to provide an independent cross-check.

## Use cases

- Number theory students inspecting the sequence of running products k! mod n to observe modular multiplicative inverses.
- Mathematics educators verifying primality test proofs with deterministic cross-checking.
- Developers validating modular arithmetic implementations against verified mathematical theorems.

## Frequently asked questions

### What is Wilson's theorem?

Wilson's theorem states that a natural number n > 1 is prime if and only if (n−1)! ≡ −1 (mod n).

### Why does the tool limit running products to n ≤ 200?

Generating and displaying the full list of intermediate residues k! mod n is restricted to n ≤ 200 to keep the output readable and performant.

### What is the composite factorial law?

For every composite number n > 4, (n−1)! ≡ 0 (mod n) because its factors appear before reaching n−1.

### Why is Wilson's theorem rarely used for massive cryptographic primes?

Computing (n−1)! takes O(n) modular operations, which becomes computationally infeasible for very large numbers compared to O(log n) tests like Miller–Rabin.

### What is the only composite exception where (n−1)! is not 0 mod n?

The only composite exception is n = 4, where (4−1)! = 3! = 6 ≡ 2 (mod 4).

## Related tools

- [Perfect Number Checker](https://elysiatools.com/en/tools/perfect-number-checker): σ(n) = 2n ⟺ perfect. Factorization-based σ(n), proper-divisor sum, deficient/perfect/abundant classification, abundancy index, Euclid–Euler form. n ≤ 10¹².
- [Prime Number Checker](https://elysiatools.com/en/tools/prime-number-checker): Check if a number is prime (a natural number greater than 1 that has no positive divisors other than 1 and itself)
- [Dimensional Analysis Unit Cancellation Tutor](https://elysiatools.com/en/tools/dimensional-analysis-unit-cancellation-tutor): Step-by-step factor-label unit cancellation with inverted-factor diagnosis and optional student-answer checking.
- [PERT Network Analyzer (Expected Duration & Variance)](https://elysiatools.com/en/tools/pert-network-analyzer): Three-point PERT estimates: te and σ² per activity, critical path, expected project duration and variance, and normal completion probability for a target time.
- [M/M/1 Queue Calculator (L, Lq, W, Wq)](https://elysiatools.com/en/tools/queuing-theory-mm1): Steady-state M/M/1 metrics: ρ, P0, L, Lq, W, Wq, state probabilities, and Little's-law cross-checks; unstable λ ≥ μ inputs are rejected.
- [M/M/c Multi-Server Queue Calculator](https://elysiatools.com/en/tools/queuing-theory-mmc): Steady-state M/M/c metrics with the Erlang-C formula: offered load, P0, Pw, Lq, L, W, Wq plus Little's-law cross-checks; unstable λ ≥ cμ inputs are rejected.
- [Combination Calculator](https://elysiatools.com/en/tools/combination-calculator): Calculate combinations (C(n,r)) with support for different types: with/without repetition, binomial coefficients, and detailed combinatorial analysis.
- [Complex Number Calculator](https://elysiatools.com/en/tools/complex-number-calculator): Perform structured arithmetic and analysis for complex numbers in algebraic and polar form

## Samples

- [Android Image Processing Java Samples](https://elysiatools.com/en/samples/android-image-processing-java): Android Java image processing examples including reading/saving images, scaling, and format conversion
- [Android Image Processing Kotlin Samples](https://elysiatools.com/en/samples/android-image-processing-kotlin): Android Kotlin image processing examples including reading/saving images, scaling, and format conversion
- [Web Image Processing Python Samples](https://elysiatools.com/en/samples/web-image-processing-python): Web Python image processing examples using PIL/Pillow including reading, saving, resizing, and format conversion
- [Web Image Processing Rust Samples](https://elysiatools.com/en/samples/web-image-processing-rust): Web Rust image processing examples including image read/save, scaling, and format conversion