Wilson's Theorem
In number theory, Wilson's Theorem states that if integer , then
is divisible by
if and only if
is prime. It was stated by John Wilson. The French mathematician Lagrange proved it in 1771.
Contents
Proofs
Suppose first that is composite. Then
has a factor
that is less than or equal to
. Then
divides
, so
does not divide
. Therefore
does not divide
.
Two proofs of the converse are provided: an elementary one that rests close to basic principles of modular arithmetic, and an elegant method that relies on more powerful algebraic tools.
Elementary proof
Suppose is a prime. Then each of the integers
has an inverse modulo
. (Indeed, if one such integer
does not have an inverse, then for some distinct
and
modulo
,
, so that
is a multiple of
, when
does not divide
or
—a contradiction.) This inverse is unique, and each number is the inverse of its inverse. If one integer
is its own inverse, then
so that
or
. Thus we can partition the set
into pairs
such that
. It follows that
is the product of these pairs times
. Since the product of each pair is congruent to
, we have
as desired.
Algebraic proof
Let be a prime. Consider the field of integers modulo
. By Fermat's Little Theorem, every nonzero element of this field is a root of the polynomial
Since this field has only
nonzero elements, it follows that
Now, either
, in which case
for any integer
,
or
is even. In either case,
, so that
If we set
equal to 0, the theorem follows.
Problems
Introductory
- (Source: ARML 2002) Let
be an integer such that
. Find the remainder when
is divided by
.
Solution
Multiplying both sides by yields
Note that
for all
. Thus we are left with
Advanced
- If
is a prime greater than 2, define
. Prove that
is divisible by
. Solution.
- Let
be a prime number such that dividing
by 4 leaves the remainder 1. Show that there is an integer
such that
is divisible by
.
See also
Category: Number Theory