Determining the Remainder of Large Factorials

Recall from the Wilson's Theorem page that Wilson's theorem states that a natural number $p$ is prime if and only if:

(1)

\begin{align} \quad (p - 1)! \equiv -1 \pmod p \end{align}

We will now use this theorem to find the remainders of large factorials.

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:

(2)

\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:

(3)

\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 an inverse of $6$ moduloe $101$. Using the division algorithm, we get that:

(4)

\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$ modulo $101$. It thus follows that:

(5)

\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:

(6)

\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 an inverse of $6$ modulo $71$ by the division algorithm:

(7)

\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:

(8)

\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!$ and we get that:

(9)

\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 an inverse of $52$ modulo $61$:

(10)

\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 of $52 $] modulo [[$ 61$. We thus get that:

(11)

\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!$:

(12)

\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 \cdot 148 \cdot ... \cdot 139 \cdot ... \cdot 1$.