Problem 17: Show that \(61! + 1 \equiv 63! + 1 \equiv 0 \pmod{71}\).
Proof
Since \(71\) is prime, then we know by Wilson’s Theorem that
$$
\begin{align*}
70! &\equiv -1 \pmod{71}
\end{align*}
$$
We can expand \(70!\) to see that
$$
\begin{align*}
(70 \cdot 69 \cdot 68 \cdot 67 \cdot 66 \cdot 65 \cdot 64) \cdot 63! &\equiv -1 \pmod{71}
\end{align*}
$$
We also know that
$$
\begin{align*}
a \cdot b \pmod{m} = (a \pmod{m}) \cdot (b \pmod{m}) \pmod{m}
\end{align*}
$$
and we know that
$$
\begin{align*}
70 &\equiv -1 \pmod{71} \\
69 &\equiv -2 \pmod{71} \\
68 &\equiv -3 \pmod{71} \\
\cdots \\
64 &\equiv -7 \pmod{71} \\
\end{align*}
$$
Then we can simplify the original product module \(71\) to
$$
\begin{align*}
(-1 \cdot -2 \cdot -3 \cdot -4 \cdot -5 \cdot -6 \cdot -7) \cdot 63! &\equiv -1 \pmod{71} \\
(-1 \cdot -2 \cdot -3 \cdot -4 \cdot -5) \cdot (-6 \cdot -7) \cdot 63! &\equiv -1 \pmod{71} \\
(-120 \cdot 42) \cdot 63! &\equiv -1 \pmod{71} \\
(22 \cdot 42) \cdot 63! &\equiv -1 \pmod{71} \\
63! &\equiv -1 \pmod{71}
\end{align*}
$$
From this, we see that
$$
\begin{align*}
63! + 1 &\equiv 0 \pmod{71}
\end{align*}
$$
Next, we want to show that \(63! + 1 \equiv 61! + 1 \pmod{71}\). To see this, observe that
$$
\begin{align*}
63! &\equiv (62 \cdot 61) \cdot 61! \pmod{71} \\
63! &\equiv (3906) \cdot 61! \pmod{71} \\
&\equiv 1 \cdot 61! \pmod{71} \\
&\equiv 61! \pmod{71}
\end{align*}
$$
Therefore
$$
\begin{align*}
63! + 1 &\equiv 61! + 1 \equiv 0 \pmod{71}
\end{align*}
$$
as desired. \(\ \blacksquare\)