I) Prove Wilson’s Theorem:
If p is a prime, then .
Proof:
The cases for primes 2 and 3 are clearly true.
Assume
Suppose that a is any one of the p-1 positive integers and consider the linear congruence
. Then,
.
Now, apply the following theorem: the linear congruence has a solution if and only if
, where
. If
, then it has d mutually incongruent solutions modulo n.
So, by the above theorem, the congruence here admits a unique solution modulo p; hence, there is a unique integer , with
, satisfying
.
Because p is prime, if and only if
or
. Indeed, the congruence
is equivalent to
. Therefore, either
, in which case
, or
, in which case
.
If we omit the numbers 1 and p-1, the effect is to group the remaining integers into pairs
and
, where
, such that the product
. When these
congruences are multiplied together and the factors rearranged, we get
or rather
Now multiply by p-1 to obtain the congruence
, which was desired to be proved.
An example to clarify the proof of Wilson’s theorem:
Specifically, let us take prime . It is possible to divide the integers
into
pairs, each product of which is congruent to 1 modulo 13. Let us write out these congruences explicitly as shown below:
Multpilying these congruences gives the result
and as
Thus, with prime
.
Further:
The converse to Wilson’s theorem is also true. If , then n must be prime. For, if n is not a prime, then n has a divisor d with
is prime if and only if
. Unfortunately, this test is of more theoretical than practical interest because as n increases,
rapidly becomes unmanageable in size.
Let us illustrate an application of Wilson’s theorem to the study of quadratic congruences{ What we mean by quadratic congruence is a congruence of the form , with
}
Theorem: The quadratic congruence , where p is an odd prime, has a solution if and only if
.
Proof:
Let a be any solution of so that
. Because
, the outcome of applying Fermat’s Little Theorem is
The possibility that for some k does not arise. If it did, we would have
Hence, . The net result of this is that
, which is clearly false. Therefore, p must be of the form
.
Now, for the opposite direction. In the product
we have the congruences
Rearranging the factors produces
because there are minus signs involved. It is at this point that Wilson’s theorem can be brought to bear; for,
, hence,
If we assume that p is of the form , then
, leaving us with the congruence
.
The conclusion is that the integer satisfies the quadratic congruence
.
Let us take a look at an actual example, say, the case , which is a prime of the form
. Here, we have
, and it is easy to see that
and
.
Thus, the assertion that is correct for
.
Wilson’s theorem implies that there exists an infinitude of composite numbers of the form . On the other hand, it is an open question whether
is prime for infinitely many values of n. Refer, for example:
https://math.stackexchange.com/questions/949520/are-there-infinitely-many-primes-of-the-form-n1
More later! Happy churnings of number theory!
Regards,
Nalin Pithwa