Wilson's Theorem

Wilson's theorem states that

a positive integer \( n > 1 \) is a prime if and only if \( (n-1)! \equiv -1 \pmod {n} \).

In other words, \( (n-1)! \) is 1 less than a multiple of \(n\). This is useful in evaluating computations of \( (n-1)! \), especially in Olympiad number theory problems. For example, since we know that 101 is a prime, we can conclude immediately that \( 100! = 101 k - 1\) for some integer \(k.\)

This statement means two things, which are as follows:

\(\quad \text{(1)}\) For a positive integer \(n\ (> 1)\), if \((n-1)!\equiv -1\pmod n,\) then \(n\) is a prime.
\(\quad \text{(2)}\) If \(p\) is a prime number, then \((p-1)!\equiv -1\pmod p\) holds.

Notice how \((1)\) 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 \(n\) even on a computer. Fortunately, we've got better primality tests to save the world! But \((2)\) is helpful in easing out computations and cracking several Olympiad number theory problems.

Let's verify Wilson's theorem for small values:

\[ \begin{array} {| l | r | c | r| } \hline n & (n-1)! & (n-1)! \pmod{n} & \text{ Is prime?} \\ \hline 2 & 1 & 1 & \text{yes} \\ 3 & 2 & 2 & \text{yes} \\ 4 & 6 & 2 & \text{no} \\ 5 & 24 & 4 & \text{yes} \\ 6 & 120 & 0 & \text{no} \\ 7 & 720 & 6 & \text{yes} \\ 8 & 5040 & 0 & \text{no} \\ 9 & 40320 & 0 & \text{no} \\ 10 & 362880 & 0 & \text{no} \\ \hline \end{array} \]

Evaluate \( 30! \pmod{899} \).

---

First, factorize \( 899 = 29 \times 31 \).
We have \( 30 ! = 30 \times 29 \times 28 ! \equiv 0 \pmod{29} \).
From Wilson's theorem, \( 30 ! \equiv -1 \pmod{31} \).
Hence, by the Chinese remainder theorem, we get that \( 30! \equiv 464 \pmod{ 899} \). \(_\square\)

Explain why \( 17 ! \equiv 1 \pmod{ 19} \).

---

From Wilson's theorem, we know that \( 18 ! \equiv -1 \pmod{19} \). Hence, dividing both sides by \( 18 \equiv -1 \pmod{19} \), we conclude that \( 17! \equiv 1 \pmod{19} \). \(_\square\)

In fact, the above example generalizes to the following:

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

If \(p\) is a prime, then by Wilson's theorem, we know that \( ( p - 1)! \equiv -1\equiv p-1 \pmod{p} \). Dividing by \( p - 1 \neq 0 \), we get that

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

Hence, \( (p-2)!\equiv 1\pmod{p}~\text{for all primes }p. \ _\square\)

Evaluate \( 97 ! \pmod{ 101} \).

---

Since \(101\) is prime, we know that \( 100 ! \equiv -1 \pmod{101} \). Hence, \( 97! \equiv \frac{ -1} { (-1)(-2)(-3) } \equiv \frac{1}{6} \pmod{101} \).
We need to find the multiplicative inverse of \(6,\) which is equal to \(17.\) Thus

\[ 97 ! \equiv 17 \pmod{101}. \ _\square\]

A positive integer \(n\ (>1)\) is a prime if and only if \((n-1)!\equiv -1\pmod n. \ _\square\)

At first glance it seems that proving \((1)\) is a really difficult job, but proving \((2)\) shouldn't be that hard. Surprisingly, the situation is exactly opposite. Proofs of \((1)\) and \((2)\) are included separately below.

\((1):\) Assuming \(n\) a composite number, we show a contradiction. If \(n\) is a composite number then it has at least one divisor \(d\) less than \(n\), that is \(d\le n-1\). But since \((n-1)!\) is the product of all positive integers from \(1\) to \(n-1\), the product must contain \(d\) and thus be divisible by \(d\). So we have \((n-1)!\equiv 0\pmod d\). Also \((n-1)!\equiv 0\not\equiv -1\pmod d\) since \(d\mid n\), contradicting the hypothesis. So \(n\) can't be composite, hence prime. \(_\square\)

\((2):\) Consider the field \(\mathbb{Z}_p\). This is just the set of integers modulo \(p\), i.e. contains all integers from \(0\) to \(p-1\). All the operations are done in modulo \(p\). For example, in this field \(5+(p-2)=3\) since \[5+(p-2)=p+3\equiv 3\pmod p.\] Now consider the polynomial \(f(x)=x^{p-1}-1\), which clearly has \(p-1\) roots by the fundamental theorem of algebra. Also \(x^{p-1}-1\equiv 0\pmod p\) for all \(1\le x\le p-1\) by Fermat's little theorem (See worked example 3 here) since \(p\) is a prime. So in \(\mathbb{Z}_p\), these must be the \(p-1\) roots of \(f\). Hence we can write

\[x^{p-1}-1=\prod_{k=1}^{p-1} (x-k)=(-1)^{p-1}\prod_{k=1}^{p-1} (k-x)=\prod_{k=1}^{p-1} (k-x)\]

because for odd primes, \(p-1\) is even, implying \((-1)^{p-1}=1,\) and for even prime \(2\) we have \((-1)^{p-1}=-1\equiv 1\pmod 2\). Now simply plugging in \(x=0\) in the last equation we get

\[-1=\prod_{k=1}^{p-1} k=(p-1)!\]

in \(\mathbb{Z}_p\). That means \((p-1)!\equiv -1\pmod p\). \(_\square\)

Prove that \(437\mid (18!+1)\).

---

First notice that \(437=19\times 23\) and so it suffices to prove that

\[18!\equiv -1\pmod{19}, \pmod{23}.\]

Now since \(19\) is a prime, \(18!\equiv -1\pmod{19}\) immediately follows by Wilson's theorem. Also noting that \(23\) is a prime, we have

\[\begin{eqnarray} 24\times 18! &=& 18!\times (-1)\times (-2)\times (-3)\times (-4) \\ &\equiv & 18!\times 19\times 20\times 21\times 22 \\ &=& 22!\stackrel{\text{Wilson's}}{\equiv} -1 \equiv -24\pmod{23}, \end{eqnarray}\]

and thus \(18!\equiv -1\pmod{23}\) as well.

Therefore, \(437\mid (18!+1)\). \(_\square\)

(ARML 2002)
Let \(a\in\mathbb{N}\) such that

\[1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots +\dfrac{1}{23}=\dfrac{a}{23!}.\]

Find \(a\pmod{13}\).

---

Rewrite the equation as

\[a=23!+\dfrac{23!}{2}+\dfrac{23!}{3}+\cdots +\dfrac{23!}{23}.\]

Clearly all the terms in the right side are integers. Also except \(\frac{23!}{13}\), all the quotients contain the factor \(13\) and thus are divisible by \(13\). Therefore, we get

\[\begin{eqnarray} a &=& 23!+\dfrac{23!}{2}+\dfrac{23!}{3}+\cdots +\dfrac{23!}{23} \\ &\equiv & \dfrac{23!}{13} = 1\times 2\times \cdots \times 12\times 14\times \cdots \times 23 \\ &\equiv & \left(1\times 2\times \cdots \times 12\right) \times \left(1\times 2\times \cdots \times 10\right) \\ &=& 12!\times 10! \stackrel{\text{Wilson's}}{\equiv} 12\times 10! \pmod{13}. \end{eqnarray}\]

So we know that \(a\equiv 12\times 10!\pmod{13}\). Now we use \(11!\equiv 1\equiv 66\pmod{13},\) which follows by Wilson's. Hence \(10!\equiv 6\pmod{13}\). Finally we have

\[a\equiv 12\times 10!\equiv 12\times 6\equiv \boxed{7}\pmod{13},\]

which is the answer. \(_\square\)

Let \( p \) be an odd prime. Let \( A = \{ a_1, a_2, \ldots , a_{p} \} \) and \(B = \{ b_1, b_2, \ldots, b_p \} \) be complete sets of residue classes modulo \(p\). Show that the set \( \left\{ a_1 b_1, a_2 b_2, \ldots , a_{p} b_{p}\right\} \) is not a complete set of residue classes.

---

We will prove by contradiction. Suppose there exist sets \(A, B \) which give us a complete set of residue classes.

First, if there exists \( i \neq j \) such that \( a_i \equiv b_j \equiv 0 \), then \( a_i b_i \equiv a_j b_j \equiv 0 \), which would not give us a complete set of residue classes. Thus, we may assume that \( a_i \equiv b_i \equiv 0 \pmod{p} \). WLOG, \( i = p \).

By Wilson's theorem, we get that \(\displaystyle \prod_{i = 1 } ^ {p-1} a_i \equiv -1 \pmod{p} \) and \(\displaystyle \prod_{i=1}^{p-1} b_i \equiv -1 \pmod{p} \).

If \( \{ a_ib_i \}_{i=1}^{p-1} \) form a complete set of non-zero residue class, then we must have

\[ -1 \equiv \prod_{i=1}^{p-1} a_i b_i \equiv \prod_{i=1}^{p-1} a_i\prod_{i=1}^{p-1} b_i \equiv (-1) \times (-1) \equiv 1 \pmod{p}. \]

Since \(p\) is an odd prime, \( p > 2 \) and we have \( -1 \not \equiv 1 \pmod{p} \), which is a contradiction. Hence, \(\{ a_i b_i \} \) is not a complete set of residue classes. \(_\square\)

1) Prove that if \( n\ (> 4) \) is composite, then \( (n-1) ! \equiv 0 \pmod{n} \).

2) Let \( p = 4k + 1 \) be a prime. Show that there exists an integer \(n\) such that \( n^2 \equiv -1 \pmod{p} \).

3) Determine all positive integers \(a\) and \(n\) such that

\[ (a-1)! + 1 = a^n. \]

4) (ISL 2000) Find all the integer solutions of \( (a^m + 1) \mid (a+1)^n \).

5) (IMO 1999/4 ) Solve for prime \(p\), with \(x\) an integer such that \( x \leq 2p \) and

\[ x ^ {p-1} \Big| \big((p-1) ^x + 1\big). \]