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{aligned} 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{aligned}$$

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{aligned} 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{aligned}$$

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).$$