# Compute the remainder when $67!$ is divided by $71$.

This is how far I've been able to get.

By using Wilson's Theorem:

\begin{align} 70! &\equiv -1 \pmod{71} \\ 67!(68)(69)(70) &\equiv -1 \pmod{71} \\ 67!(68)(69)(-1) &\equiv -1 \pmod{71} \\ 67!(68)(69) &\equiv 1 \pmod{71} \\ \end{align}

EDIT: Here is how I proceeded using TMM's and Carl Mummert's hints.

\begin{align} &68 \equiv -3 \pmod{71}\\ and\\ &69 \equiv -2 \pmod{71}\\ \end{align}

So: \begin{align} 67!(-3)(-2) &\equiv 1 \pmod{71} \\ 67! &\equiv 6^{-1} \pmod{71} \\ \end{align}

By using the Euclidean algorithm: $$71 = 6 \cdot 11 + 5$$ $$6 = 5 \cdot 1 + 1$$ $$5 = 1 \cdot 5 + 0$$

Now, going backwards: \begin{align} 1 &= 6 - 5 \\ &= 6 - (71 - 6 \cdot 11) \\ &= 6 + 6(11) - 71 \\ &= 6(1 + 11) - 71(1) \\ &= 6(12) - 71(1) \end{align}

Therefore, $67! \equiv 6^{-1} \equiv 12 \pmod{71}$.

-
So $67! = 69^{-1}68^{-1}\pmod{71}$. Compute those two inverses and you're done. – Carl Mummert May 12 '13 at 20:12
You should consider using $\cdot$ instead of $*$ to denote multiplication for two reasons. Typically, $*$ denotes convolution and $*$ looks ugly when you use it for multiplication. – user17762 May 12 '13 at 20:46
The first steps can be condensed by replacing -1 with 70 right at the outset. – Kaz May 12 '13 at 21:39

Hint: $$69 \equiv -2 \pmod{71}, \qquad 68 \equiv -3\pmod{71}.$$ Further hint: $72 = 6 \cdot 12$, so the inverse you need to compute should not be too difficult...
@icanc: For small numbers it usually helps to just try and see. As the inverse $x$ of $6$ must be between $1$ and $70$, we must have $6 \leq 6x \leq 420$ and therefore $6x \in \{72, 143, 214, 285, 356\}$. We can already eliminate the two odd numbers, and if necessary check the other three by hand. – TMM May 12 '13 at 20:26
Recall that if $$xy \equiv a \pmod{n}$$ then $$x \equiv ay^{-1} \pmod{n}$$ if $y$ is invertible in $\pmod{n}$. In your case, $n$ is $71$ a prime, which guarantees that any $y \not \equiv 0 \pmod{71}$ is invertible in $\pmod{71}$. Hence,, we have $$67! \times 68 \times 69 \equiv 1 \pmod{71} \implies 67! \equiv (69)^{-1} (68)^{-1} \pmod{71}$$ We have \begin{align} 68 \times 47 - 71 \times 45 & = 1\\ 69 \times 35 - 71 \times 34 & = 1 \end{align} Hence, $$(68)^{-1} \equiv 47 \pmod{71} \text{ and }(69)^{-1} \equiv 35 \pmod{71}$$ Hence, $$67!\equiv 35 \times 47 \pmod{71} \equiv 12 \pmod{71}$$