Wilson's Theorem

From Canonica AI

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.

A visual representation of Wilson's theorem, showing a sequence of numbers and their factorial values.
A visual representation of Wilson's theorem, showing a sequence of numbers and their factorial values.

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.

See Also

Categories