3.5.3 Wilson’s Theorem

I’ve seen a couple of questions in the latter stages of the number sense question which asks something along the lines of:

$$6! \cong x (\text{mod } 7), 0 \le x \le 6, x = ?$$

Questions like this use the result from Wilson’ Theorem which states:

For prime $p$, $(p - 1)! \cong (p - 1) (\text{mod } p)$

So using the above Theorem, we know that $6! \cong x (\text{mod } 7), 0 \le x \le 6, x = 6$.

It is essentially for $p$ to be prime Wilson’s Theorem to be applicable. Usually, with factorial problems, you can lump common factors and then can check divisibility. For example:

$$4! \cong x (\text{mod } 6), 0 \le x \le 5, x = ?$$

Well we know that $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 4 \cdot 6 \cong 0 (\text{mod } 6) \Rightarrow x = 0$.

The following are some more problems to give you some practice:

Problem Set 3.5.3