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
[hide]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 .