Number Theory · step 12 of 13

Wilson’s theorem & primality testing

Wilson’s theorem states that (p−1)! ≡ −1 (mod p) if and only if p is prime — a genuine characterisation, unlike Fermat’s one-way test. It is useless computationally, since computing a factorial is far harder than trial division, but it is a clean theoretical criterion and a favourite exam target for small moduli.

Practise wilson’s theorem & primality testing free → All Number Theory subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

State the theorem in both directionsp prime implies (p−1)! ≡ −1; and conversely, so it is an iff.
Pair elements with their inverses to see whyIn ℤ/pℤ every element except 1 and p−1 pairs with a distinct inverse, so the product collapses to 1·(p−1) ≡ −1.
Use it for small computationsFor p = 7, 6! = 720 = 102·7 + 6 ≡ −1 (mod 7) ✓.
Compare with practical testsTrial division to √n for small n; Miller–Rabin for large n; AKS for a deterministic polynomial-time guarantee.

Worked example

Verify Wilson’s theorem for p = 11.

Pair each element with its inverse mod 11: 2·6 = 12 ≡ 1, 3·4 = 12 ≡ 1, 5·9 = 45 ≡ 1, 7·8 = 56 ≡ 1.
That accounts for 2 through 9, each pair contributing 1.
The unpaired elements are 1 and 10, since each is its own inverse.
So 10! ≡ 1 × 10 ≡ 10 ≡ −1 (mod 11).

Answer. 10! ≡ −1 (mod 11), confirming Wilson’s theorem — and the pairing argument is the proof in miniature.

Where marks get dropped

These are the specific errors that cost credit on wilson’s theorem & primality testing questions — QED's rubric penalises each of them separately.

Trying to use Wilson as a practical primality test. Computing (n−1)! costs far more than trial division.
Forgetting that 1 and p−1 are self-inverse, which is exactly why the product is −1 rather than 1.
Confusing Wilson with Fermat. Wilson is an iff; Fermat’s test can be passed by composites.

Practise this until it is automatic

Unlimited fresh questions

QED generates new wilson’s theorem & primality testing problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Number Theory mastery is tracked so you know when this is exam-ready.

Wilson’s theorem & primality testing — frequently asked questions

Why is Wilson’s theorem an iff?

For composite n > 4, n divides (n−1)! because its factors appear among 1…n−1, so (n−1)! ≡ 0, not −1. Only primes give −1.

What is Miller–Rabin?

A probabilistic test refining Fermat by also checking square roots of 1. Each round rejects a composite with probability at least 3/4, and it is not fooled by Carmichael numbers.

Is primality testing in P?

Yes — the AKS algorithm (2002) is deterministic polynomial time. In practice Miller–Rabin is used because it is far faster.

The rest of Number Theory

Divisibility, primes, gcd, modular arithmetic. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make wilson’s theorem & primality testing exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →