# 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

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