Wilson’s theorem and related problems in Elementary Number Theory for RMO

I) Prove Wilson’s Theorem:

If p is a prime, then (p-1)! \equiv -1 {\pmod p}.

Proof:

The cases for primes 2 and 3 are clearly true.

Assume p>3

Suppose that a is any one of the p-1 positive integers 1,2,3, \ldots {p-1} and consider the linear congruence
ax \equiv 1 {\pmod p}. Then, gcd(a,p)=1.

Now, apply the following theorem: the linear congruence ax \equiv b {\pmod n} has a solution if and only if d|b, where d = gcd(a,b). If d|b, 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 a^{'}, with 1 \leq a^{'} \leq p-1, satisfying aa^{'} \equiv 1 {\pmod p}.

Because p is prime, a = a^{'} if and only if a=1 or a=p-1. Indeed, the congruence a^{2} \equiv 1 {\pmod p} is equivalent to (a-1)(a+1) \equiv 0 {\pmod p}. Therefore, either a-1 \equiv 0 {\pmod p}, in which case a=1, or a+1 \equiv 0 {\pmod p}, in which case a=p-1.

If we omit the numbers 1 and p-1, the effect is to group the remaining integers 2,3, \ldots (p-2) into pairs a and a^{'}, where a \neq a^{'}, such that the product aa^{'} \equiv 1 {\pmod p}. When these (p-3)/2 congruences are multiplied together and the factors rearranged, we get

2.3. \ldots (p-2) \equiv 1 {\pmod p}

or rather

(p-2)! \equiv 1 {\pmod p}

Now multiply by p-1 to obtain the congruence

(p-1)! \equiv p-1 \equiv -1 {\pmod p}, which was desired to be proved.

An example to clarify the proof of Wilson’s theorem:

Specifically, let us take prime p=13. It is possible to divide the integers 2,3,4, \ldots, 11 into (p-3)/2=5 pairs, each product of which is congruent to 1 modulo 13. Let us write out these congruences explicitly as shown below:

2.7 \equiv 1 {\pmod {13}}
3.9 \equiv 1 {\pmod {13}}
4.10 \equiv 1 {\pmod {13}}
5.8 \equiv 1 {\pmod {13}}
6.11 \equiv 1 {\pmod {13}}

Multpilying these congruences gives the result 11! = (2.7)(3.9)(4.10)(5.8)(6.11) \equiv 1 {\pmod {13}}

and as 12! \equiv 12 \equiv -1 {\pmod {13}}

Thus, (p-1)! \equiv -1 {\pmod p} with prime p=13.

Further:

The converse to Wilson’s theorem is also true. If (n-1)! \equiv -1 {\pmod n}, then n must be prime. For, if n is not a prime, then n has a divisor d with 1 1 is prime if and only if (n-1)! \equiv -1 {\pmod n}. Unfortunately, this test is of more theoretical than practical interest because as n increases, (n-1)! 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 ax^{2}+bx+c \equiv 0 {\pmod n}, with a \not\equiv 0 {\pmod n} }

Theorem: The quadratic congruence x^{2}+1 \equiv 0 {\pmod p}, where p is an odd prime, has a solution if and only if p \equiv 1 {\mod 4}.

Proof:

Let a be any solution of x^{2}+1 \equiv 0 {\pmod p} so that a^{2} \equiv -1 {\pmod p}. Because p \not |a, the outcome of applying Fermat’s Little Theorem is

1 \equiv a^{p-1} \equiv (a^{2})^{(p-1)/2} \equiv (-1)^{(p-1)/2} {\pmod p}

The possibility that p=4k+3 for some k does not arise. If it did, we would have

(-1)^{(p-1)/2} = (-1)^{2k+1} = -1

Hence, 1 \equiv -1 {\pmod p}. The net result of this is that p|2, which is clearly false. Therefore, p must be of the form 4k+1.

Now, for the opposite direction. In the product

(p-1)! = 1.2 \ldots \frac{p-1}{2} \frac{p+1}{2} \ldots (p-2)(p-1)

we have the congruences

p-1 \equiv -1 {\pmod p}
p-2 \equiv -2 {\pmod p}
p-3 \equiv -3 {\pmod p}
\vdots
\frac{p+1}{2} \equiv - \frac{p-1}{2} {\pmod p}

Rearranging the factors produces
(p-1)! \equiv 1.(-1).2.(-2) \ldots \frac{p-1}{2}. (-\frac{p-1}{2}) {\pmod p} \equiv (-1)^{(p-1)/2}(.2. \ldots \frac{p-1}{2})^{2}{\pmod p}

because there are (p-1)/2 minus signs involved. It is at this point that Wilson’s theorem can be brought to bear; for, (p-1)! \equiv -1 {\pmod p}, hence,

-1 \equiv (-1)^{(p-1)/2}((\frac{p-1}{2})!)^{2} {\pmod p}

If we assume that p is of the form 4k+1, then (-1)^{(p-1)/2} =1, leaving us with the congruence

-1 \equiv (-\frac{p-1}{2})^{2}{\pmod p}.

The conclusion is that the integer (\frac{p-1}{2})! satisfies the quadratic congruence x^{2}+1 \equiv 0 {\pmod p}.

Let us take a look at an actual example, say, the case p=13, which is a prime of the form 4k+1. Here, we have \frac{p-1}{2}=6, and it is easy to see that 6! = 720 \equiv 5 {\pmod {13}} and 5^{2}+1 = 26 \equiv 0 {\pmod {13}}.

Thus, the assertion that ((p-1)!)^{2}+1 \equiv 0 {\pmod p} is correct for p=13.

Wilson’s theorem implies that there exists an infinitude of composite numbers of the form n!+1. On the other hand, it is an open question whether n!+1 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.