# Examples of Finding Remainders Using Wilson's Theorem

For the following questions, we will be frequently using Wilson's Theorem which states that for a prime p, $(p - 1)! \equiv -1 \pmod {p}$.

## Example 1

**Find the remainder of 97! when divided by 101.**

First we will apply Wilson's theorem to note that $100! \equiv -1 \pmod {101}$. When we decompose the factorial, we get that:

(1)Now we note that $100 \equiv -1 \pmod {101}$, $99 \equiv -2 \pmod {101}$, and $98 \equiv -3 \pmod {101}$. Hence:

(2)Now we want to find a modular inverse of 6 (mod 101). Using the division algorithm, we get that:

(3)Hence, 17 can be used as an inverse for 6 (mod 101). It thus follows that:

(4)Hence, 97! has a remainder of 17 when divided by 101.

## Example 2

**Find the remainder of 67! when divided by 71.**

Using Wilson's theorem, we have that $70! \equiv -1 \pmod {71}$. Decomposing the factorial we get that:

(5)Now let's find a modular inverse of 6 (mod 71) by the division algorithm:

(6)Hence, 12 can be used as an inverse. Thus:

(7)Hence when 67! is divided by 71, the remainder leftover is 12.

## Example 3

**Find the remainder of 53! when divided by 61.**

We know that by Wilson's theorem $60! \equiv -1 \pmod {61}$. Decomposing 60!, we get that:

(8)We will now use the division algorithm to find a modular inverse of 52 (mod 61):

(9)Hence 27 can be used as an inverse (mod 61). We thus get that:

(10)Hence the remainder of 51! when divided by 61 is 27.

## Example 4

**What is the remainder of 149! when divided by 139?**

From Wilson's theorem we know that $138! \equiv -1 \pmod {139}$. We are now going to multiply both sides of the congruence until we get up to 149!:

(11)Hence the remainder of 149! when divided by 139 is 0.

In fact, this should make sense, since 149! = 149 x 148 x … x 139 x 138 x … x 2 x 1. For any primes p and q where p > q, it follows that $(p - 1)! \equiv 0 \pmod {q}$.