TAOCP 1.2.5 Exercise 13

Section 1.2.5: Permutations and Factorials

Exercise 13. [**] [M23] (Wilson's theorem, actually due to Leibniz, 1682.) If $p$ is prime, then $(p-1)! \bmod p = p-1$. Prove this, by pairing off numbers among ${1,2,\ldots,p-1}$ whose product modulo $p$ is $1$.

x 14. [M28] (L. Stickelberger, 1890.) In the notation of exercise 12, we can determine $n! \bmod p$ in terms of the $p$-ary representation, for any positive integer $n$, thus generalizing Wilson's theorem. In fact, prove that

$$ \frac{n!}{p^\mu} \equiv (-1)^\mu a_0!a_1!\cdots a_k! \pmod p. $$

Verified: yes
Solve time: 8m39s

---

Let

$$ S={1,2,\ldots,p-1}, $$

where $p$ is prime. We must prove that

$$ (p-1)! \equiv p-1 \pmod p, $$

or equivalently,

$$ (p-1)! \equiv -1 \pmod p. $$

Since $p$ is prime, every element $a\in S$ is relatively prime to $p$. Therefore $a$ has a unique multiplicative inverse modulo $p$; that is, there exists a unique $a^{-1}\in S$ such that

$$ aa^{-1}\equiv 1 \pmod p. $$

Pair each element of $S$ with its inverse. If $a\neq a^{-1}$, then the pair ${a,a^{-1}}$ contributes

$$ aa^{-1}\equiv 1 \pmod p $$

to the product

$$ 1\cdot2\cdots(p-1). $$

The only elements that are not paired with a distinct partner are those satisfying

$$ a\equiv a^{-1}\pmod p. $$

Multiplying by $a$, we obtain

$$ a^2\equiv 1\pmod p, $$

hence

$$ (a-1)(a+1)\equiv 0\pmod p. $$

Because $p$ is prime, this implies

$$ a\equiv 1\pmod p \quad\text{or}\quad a\equiv -1\pmod p. $$

Within $S$, these are precisely the elements $1$ and $p-1$.

Therefore all elements of $S$ except $1$ and $p-1$ can be grouped into distinct inverse pairs, each pair having product $1$ modulo $p$. Consequently,

$$ (p-1)! \equiv 1\cdot(p-1)\cdot \prod_{\text{inverse pairs }{a,a^{-1}}} aa^{-1} \pmod p. $$

Each paired factor equals $1$ modulo $p$, so

$$ (p-1)! \equiv 1\cdot(p-1) \equiv p-1 \pmod p. $$

Hence

$$ \boxed{(p-1)! \equiv p-1 \pmod p}, $$

which is Wilson's theorem. ∎