Wilson's theorem states that
a positive integer is a prime if and only if .
In other words, is 1 less than a multiple of . This is useful in evaluating computations of , especially in Olympiad number theory problems. For example, since we know that 101 is a prime, we can conclude immediately that for some integer
This statement means two things, which are as follows:
For a positive integer , if then is a prime.
If is a prime number, then holds.
Notice how provides us with a way to check if a number is prime. But this is really inefficient as factorials grow really fast. So it's hard to compute the modulus for sufficiently large even on a computer. Fortunately, we've got better primality tests to save the world! But is helpful in easing out computations and cracking several Olympiad number theory problems.
Let's verify Wilson's theorem for small values:
First, factorize .
We have .
From Wilson's theorem, .
Hence, by the Chinese remainder theorem, we get that .
Explain why .
From Wilson's theorem, we know that . Hence, dividing both sides by , we conclude that .
In fact, the above example generalizes to the following:
If is a prime, then .
If is a prime, then by Wilson's theorem, we know that . Dividing by , we get that
Since is prime, we know that . Hence, .
We need to find the multiplicative inverse of which is equal to Thus
A positive integer is a prime if and only if
At first glance it seems that proving is a really difficult job, but proving shouldn't be that hard. Surprisingly, the situation is exactly opposite. Proofs of and are included separately below.
Assuming a composite number, we show a contradiction. If is a composite number then it has at least one divisor less than , that is . But since is the product of all positive integers from to , the product must contain and thus be divisible by . So we have . Also since , contradicting the hypothesis. So can't be composite, hence prime.
Consider the field . This is just the set of integers modulo , i.e. contains all integers from to . All the operations are done in modulo . For example, in this field since Now consider the polynomial , which clearly has roots by the fundamental theorem of algebra. Also for all by Fermat's little theorem (See worked example 3 here) since is a prime. So in , these must be the roots of . Hence we can write
because for odd primes, is even, implying and for even prime we have . Now simply plugging in in the last equation we get
in . That means .
Prove that .
First notice that and so it suffices to prove that
Now since is a prime, immediately follows by Wilson's theorem. Also noting that is a prime, we have
and thus as well.
Let such that
Rewrite the equation as
Clearly all the terms in the right side are integers. Also except , all the quotients contain the factor and thus are divisible by . Therefore, we get
So we know that . Now we use which follows by Wilson's. Hence . Finally we have
which is the answer.
Let be an odd prime. Let and be complete sets of residue classes modulo . Show that the set is not a complete set of residue classes.
We will prove by contradiction. Suppose there exist sets which give us a complete set of residue classes.
First, if there exists such that , then , which would not give us a complete set of residue classes. Thus, we may assume that . WLOG, .
By Wilson's theorem, we get that and .
If form a complete set of non-zero residue class, then we must have
Since is an odd prime, and we have , which is a contradiction. Hence, is not a complete set of residue classes.
1) Prove that if is composite, then .
2) Let be a prime. Show that there exists an integer such that .
3) Determine all positive integers and such that
4) (ISL 2000) Find all the integer solutions of .
5) (IMO 1999/4 ) Solve for prime , with an integer such that and