Wilson's Theorem
Introduction
Wilson's theorem is a statement in number theory, named after the British mathematician John Wilson. This theorem is a fundamental concept in the field of number theory, providing a criterion for determining whether a number is prime.
Statement of the Theorem
The theorem is stated as follows: A natural number n > 1 is a prime number if and only if (n-1)! ≡ -1 (mod n). In other words, the factorial of (n-1) is congruent to -1 modulo n, if and only if n is a prime number.
Proof of Wilson's Theorem
The proof of Wilson's theorem involves the use of several concepts in number theory, including modular arithmetic, factorials, and congruences.
Proof for p is prime
When p is prime, the integers from 1 to p-1 each have a unique multiplicative inverse modulo p. If p > 2, we can pair each number with its inverse, and the product of each pair is 1. The two numbers that are their own inverses are 1 and -1 ≡ p-1 (mod p). Therefore, (p-1)! ≡ 1 * (p-1) ≡ -1 (mod p).
Proof for p is composite
When p is composite, there is at least one number a (1 < a < p-1) that divides p. This means that a * b ≡ 0 (mod p) for some b (1 ≤ b < p), which implies that (p-1)! ≡ 0 (mod p). Therefore, (p-1)! cannot be congruent to -1 (mod p), and p is not prime.
Applications of Wilson's Theorem
Wilson's theorem has many applications in number theory and cryptography. For example, it is used in the AKS primality test, a deterministic algorithm that can determine whether a number is prime in polynomial time. It is also used in the construction of hash functions and public-key cryptography systems.