What is the remainder of $65!$ divided by $67$?

Question

What is the remainder of $65!$ divided by $67$?

---

Attempt:

By Wilson's theorem, we have $66! = -1\mod(67) $.

$$66! = -1\mod(67) \implies 66 (65!) = -1 \mod(67)$$

and we also know that $66 = -1 \mod(67)$, then we have $$66 (65!) = -1 \mod(67) \implies -65! = -1 \mod (67)$$

so the remainder is 1. Is this the only approach?

Answer 1

This is the most natural approach. Since you seem to be seeking different methods I will mention a generalization (Wilson Reflection Formula) from a slightly different viewpoint.

An equivalent way to state Wilson's theorem is that any complete system of representatives of nonzero remainders mod $\,p\,$ has product $\equiv -1.\,$ In particular this is true for any sequence of $\,p\,$ consecutive integers, after removing its $\rm\color{#c00}{multiple}$ of $\,p.\,$ Thus the standard remainder sequence when left-shifted by $\,k\,$ i.e. $\,{-}k,\ldots,-1,\require{cancel}\cancel{\color{#c00}0,} 1,2,\ldots,\, p\!-\!1\!-\!k\,$ has product $\,(-1)^k k!\, (p\!-\!1\!-\!k)!\equiv -1\pmod{\!p},\, $ so

$$\qquad\qquad (p\!-\!1\!-\!k)!\, \equiv\, \dfrac{(-1)^k}{k!}\! \pmod{\!p}\qquad [\text{Wilson Reflection Formula}]$$

The OP is the special case $\, k = 1\,$ (leftshift by $1)$

Remark $\ $ The essence of Wilson's theorem is group-theoretical, so if you know a little group theory I highly recommend that you look at some prior posts on the group-theoretic viewpoint, which more clearly highlight the innate involution symmetry (negation/inversion "reflection")

Answer 2

$66!\equiv 66\bmod 67\implies 65!\equiv 1\bmod 67$

You could use $$65!\equiv -((33!)^2)\bmod 67$$ But then it comes down to finding 33! mod 67.

There are probably even more methods, But none is as quick as realizing $${ -1 \over -1}\equiv 1$$ Which is what Wilson's Theorem tells us.

Answer 3

You could use the fact that in the field $\mathbb{F}_{67}$, the only elements that are their own (multiplicative) inverses are $1$ and $66$. So the elements $2, 3, ..., 65$ can be paired off into inverse pairs. Each pair multiplies to $1$.

Having said that: That idea is often used as a proof of Wilson's Theorem.

Answer 4

Every number in the range $[1,66]$ has a multiplicative inverse because 67 is prime. Also, the equation $x^2 - 1 \equiv 0 \pmod{67}$ can be written as $(x+1)(x-1) \equiv 0 \pmod{67}$. SInce 67 is prime, the only solutions are 1 and 66. This means that the range [2, 65] is composed of 32 pairs of numbers, where each pair of numbers are each other's multiplicative inverse

It follows that $65! \equiv 1 \pmod{67}$