Remainder of $22!$ upon division with $23$?

Question

I couldn't solve the problem, but I came to know the answer is $22$.

Then I tried to check the numbers in factorial will be cancelled by their modulo inverses w.r.t $23$. But they didn't. \begin{array}{|c|c|} \hline \text{Number} & \text{Modulo Inverse w.r.t 23} \\ \hline 2 & 1 \\ 3 & 2 \\ 4 & 3 \\ 5 & 2 \\ 6 & 5 \\ 7 & 4 \\ 8 & 7 \\ 9 & 2 \\ 10 & 7 \\ 11 & 1 \\ 12 & 11 \\ 13 & 4 \\ 14 & 11 \\ 15 & 2 \\ 16 & 7 \\ 17 & 3 \\ 18 & 11 \\ 19 & 5 \\ 20 & 7 \\ 21 & 11 \\ 22 & 1 \\ \hline \end{array}

How to solve this problem?

Answer 1

Wilson's theorem states that if $p$ is prime, then

$$(p-1)! \equiv -1 \pmod p$$

Note that $23$ is a prime, hence $22! \equiv 22 \pmod{23}$.

Answer 2

Your (multiplicative) inverses should be $$2\times 12=3\times 8=4\times 6=24\equiv 1 \bmod 23$$ $$5\times 14=7\times 10=70\equiv 1\bmod 23$$ $$9\times 18 \equiv 1 \bmod 23 $$ $$11\times21=231\equiv 1\bmod 23$$$$13\times 16=208\equiv 1 \bmod 23$$$$15\times 20=299\equiv 1 \bmod 23$$$$17\times 19=323\equiv 1 \bmod 23$$

You are left with $0$ which isn't part of the product, $1$ and $22\equiv -1$.

So you get a product of $1$s with just one $-1$ to give $-1\bmod 23$

---

Note: I used some tricks to make this easier eg $4\times 6 =-4\times -6 \equiv 19\times 17$

The fact that $23$ is prime guarantees that the numbers other than $0, \pm 1$ will pair up in this way, and this is one way of proving Wilson's Theorem.