TAOCP 5.1.3 Exercise 5

Section 5.1.3: Runs

Exercise 5. [M20] [M20] Deduce the value of $(p!) \bmod p$ when $p$ is prime.

Verified: yes
Solve time: 1m48s

Solution

Let $p$ be a prime. The factorial $p!$ is defined as

$p! = 1 \cdot 2 \cdot 3 \cdots (p-1) \cdot p.$

The factor $p$ appears explicitly in this product. Hence there exists an integer

$k = 1 \cdot 2 \cdot 3 \cdots (p-1)$

such that

$p! = p \cdot k.$

This expresses $p!$ as a multiple of $p$, so $p \mid p!$. Therefore the remainder of $p!$ upon division by $p$ is $0$, which means

$p! \equiv 0 \pmod p.$

Thus,

$\boxed{(p!) \bmod p = 0}.$

∎