Examples of Finding Remainders Using Wilson's Theorem

# 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)
\begin{align} (100)(99)(98)(97!) \equiv -1 \pmod {101} \end{align}

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

(2)
\begin{align} (-1)(-2)(-3)(97!) \equiv -1 \pmod {101} \\ (-6)(97!) \equiv -1 \pmod {101} \\ (6)(97!) \equiv 1 \pmod {101} \end{align}

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

(3)
\begin{align} 101 = 6(16) + 5 \\ 6 = 5(1) + 1 \\ 1 = 6 + 5(-1) \\ 1 = 6 + [101 + 6(-16)](-1) \\ 1 = 101(-1) + 6(17) \end{align}

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

(4)
\begin{align} (17)(6)(97!) \equiv (17)1 \pmod {101} \\ 97! \equiv 17 \pmod {101} \end{align}

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)
\begin{align} (70)(69)(68)(67!) \equiv -1 \pmod {71} \\ (-1)(-2)(-3)(67!) \equiv -1 \pmod {71} \\ (-6)(67!) \equiv -1 \pmod {71} \\ 6(67!) \equiv 1 \pmod {71} \end{align}

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

(6)
\begin{align} 71 = 6(11) + 5 \\ 6 = 5(1) + 1 \\ 1 = 6 + 5(-1) \\ 1 = 6 + [71 + 6(-11)](-1) \\ 1 = 71(-1) + 6(12) \end{align}

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

(7)
\begin{align} (12)(6)(67!) \equiv (12)(1) \pmod {71} \\ 67! \equiv 12 \pmod {71} \end{align}

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)
\begin{align} (60)(59)(58)(57)(56)(55)(54)(53)(52)51! \equiv -1 \pmod {61} \\ (-1)(-2)(-3)(-4)(-5)(-6)(-7)(-8)(-9)51! \equiv -1 \pmod {61} \\ (-362880)51! \equiv -1 \pmod {61} \\ (362880)51! \equiv 1 \pmod {61} \\ (52)51! \equiv 1 \pmod {61} \end{align}

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

(9)
\begin{align} 61 = 52(1) + 9 \\ 52 = 9(5) + 7 \\ 9 = 7(1) + 2 \\ 7 = 2(3) + 1 \\ 1 = 7 + 2(-3) \\ 1 = 7 + [9 + 7(-1)](-3) \\ 1 = 9(-3) + 7(4) \\ 1 = 9(-3) + [52 + 9(-5)](4) \\ 1 = 52(4) + 9(-23) \\ 1 = 52(4) + [61 + 52(-1)](-23) \\ 1 = 61(-23) + 52(27) \end{align}

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

(10)
\begin{align} (27)(52)51! \equiv (27)1 \pmod {61} \\ 51! \equiv 27 \pmod {61} \end{align}

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)
\begin{align} 149! \equiv (149)(148)(147)(146)(145)(144)(143)(142)(141)(140)(139)(-1) \pmod {139} \\ 149! \equiv (10)(9)(8)(7)(6)(5)(4)(3)(2)(1)(0)(-1) \pmod {139} \\ 149! \equiv 0 \pmod {139} \\ \end{align}

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