✦ScienexySCIENCE KNOWLEDGE LIBRARY
theorem · SCI-MAT-002-080

Wilson's Theorem

Wilson's Theorem states that an integer p greater than 1 is prime if and only if (p − 1)! is congruent to −1 modulo p.

p is prime ⇔ (p − 1)! ≡ −1 (mod p), for p > 1

Explanation

Wilson's Theorem provides a necessary and sufficient condition for primality. It states that an integer p > 1 is prime exactly when (p − 1)! ≡ −1 (mod p). Here, the factorial (p − 1)! represents the product of all positive integers from 1 to p − 1. When p is prime, every nonzero residue modulo p has a multiplicative inverse. In the product 1 × 2 × ... × (p − 1), each element can be paired with its inverse, and the only elements that are their own inverses modulo p are 1 and −1. Their product is therefore congruent to −1 modulo p. The converse also holds: if the factorial congruence is satisfied for an integer greater than 1, that integer must be prime. Although Wilson's Theorem gives an exact characterization of prime numbers, calculating large factorials makes it inefficient as a practical primality test.

Variables

P

An integer greater than 1 being tested for primality.

(p − 1)!

The factorial of p − 1, equal to 1 × 2 × ... × (p − 1).

Mod p

Reduction modulo p.

−1

The residue equivalent to p − 1 modulo p.

Example or application

Problem

Verify Wilson's Theorem for p = 5.

Solution

Calculate (5 − 1)! = 4! = 1 × 2 × 3 × 4 = 24. Dividing 24 by 5 leaves a remainder of 4. Since 4 ≡ −1 (mod 5), the theorem is satisfied, confirming that 5 is prime.

Answer

4! ≡ 24 ≡ 4 ≡ −1 (mod 5)

Text

Wilson's Theorem characterizes prime integers through a factorial congruence. It is theoretically important in number theory, although its direct computational use is limited for large integers.

Key Points

  • Wilson's Theorem applies to integers greater than 1.

  • An integer p is prime if and only if (p − 1)! ≡ −1 (mod p).

  • The factorial includes every positive integer smaller than p.

  • The theorem is both necessary and sufficient for primality.

  • Its proof uses the existence and pairing of multiplicative inverses modulo a prime.

  • Direct calculation becomes inefficient for large values of p.

Applications

  • Theoretical characterization of prime numbers.

  • Elementary proofs in number theory.

  • Studying multiplicative inverses modulo primes.

  • Demonstrating relationships between factorials and modular arithmetic.

  • Constructing mathematical exercises involving primality.

Learning Outcomes

  • State Wilson's Theorem.

  • Use the theorem to verify the primality of small integers.

  • Calculate factorials modulo a given integer.

  • Explain the theoretical importance and computational limitations of the theorem.

Practice Questions

  • Verify Wilson's Theorem for p = 3.

  • Calculate 6! modulo 7.

  • Use Wilson's Theorem to test whether 7 is prime.

  • Evaluate 4! modulo 6 and explain why it does not satisfy the prime condition.

  • Explain why Wilson's Theorem is not generally an efficient practical primality test for large integers.

Related Concepts

  • Prime Numbers

  • Factorials

  • Modular Inverses

  • Fermat's Little Theorem

  • Congruence Relations

Common Mistakes

  • Using p! instead of (p − 1)!.

  • Forgetting that the theorem applies to integers greater than 1.

  • Treating −1 modulo p as a negative remainder instead of the residue p − 1.

  • Assuming that Wilson's Theorem is computationally efficient for very large numbers.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Kenneth H. Rosen, Elementary Number Theory and Its Applications
  • David M. Burton, Elementary Number Theory

Suggest a correction or source · More in Arithmetic & Number Theory