How to prove the Modulo of a Factorial

Question

So given $16! = -1 (mod 17)$ Where the factorial $16!$ is not larger than $(mod 17)$

I know that I can use Wilson's theorem to deduct this, but how would I go about showing evidence?

Answer 1

The heart of Wilson's theorem is that $\mathbb Z_{17}-\{0\}$ is a field.

So look for the multiplicative inverses.

$1 \equiv 18 \mod 17$ so $2*9\equiv 1 \mod 17$ and $3*6 \equiv 1 \mod 17$. So $2\leftrightarrow 9$ and $3\leftrightarrow 6$ are inverses.

$4 = 2^2$ so $9^2 = 81 \equiv 13$ and $4*13=52 \equiv 1 \mod 17$ so $4\leftrightarrow 13$ are inverses.

$5*x \equiv 1 \equiv 35 = 5*7\mod 17$ so $5\leftrightarrow 7$ are inverses.

$8 = 2*4$ so $9*13= 117\equiv 15 \mod 17$ so $8*15= 120=10*12 \equiv 1\mod 17$ so $8\leftrightarrow 15$ are inverses as are $10\leftrightarrow 12$.

We have only $11,14$ and $16$ left and we know $16 \equiv -1 \mod 17$.

$14 = 2*7$ so $9*5 = 45 \equiv 11$ and $14*11= 154\equiv 1 \mod 17$. So $14\leftrightarrow 11$ are inverses.

So $16! = (2*9)(3*6)(4*13)(5*7)(8*15)(10*12)(11*14)*16 \equiv 1*1*1*1*1*1*1*1*-1 \equiv -1 \mod 17$.

=====

Although in my opinion that was hard and tedious and it might be easier just to do it by brute force.

$2*3*4=24\equiv 7 \mod 17$.

$7*5 = 35\equiv 1 \mod 17$.

$6*7 = 42 \equiv 8\mod 17$

$8*8 = 4*16\equiv -4 \equiv 13 \mod 17$.

$-4*9 \equiv -36 \equiv - 2\mod 17$.

$-2*10 \equiv -20 \equiv -3 \mod 17$.

$-3*11 \equiv -33 \equiv 1 \mod 17$.

$12*13 \equiv -5*-4 \equiv 20 \equiv 3 \mod 17$.

$3*14 = 42 \equiv 8\mod 17$

$8*15 \equiv 8*(-2)=-16\equiv 1 \mod 17$.

$16 \equiv -1 \mod 17$.

So $16! \equiv -1 \mod 17$. (But it's very easy to make an mistake.)

Answer 2

Alternatively: we want to find $a$ in: $$16!\equiv a \pmod{17}.$$ By continuously applying symmetry: $$\begin{align}16!=&1\cdot (17-1)\cdot 2\cdot (17-2)\cdots 8\cdot (17-8) \equiv \\ &1\cdot (-1)\cdot 2\cdot (-2)\cdots 8\cdot (-8)\equiv \\ & ((1\cdot 8)\cdot (2\cdot 7)\cdot (3\cdot 6)\cdot (4\cdot 5))^2 \equiv \\ &(8\cdot (-3)\cdot 1\cdot 3)^2 \equiv((8\cdot 3)\cdot (-3))^2\equiv \\ &(7\cdot 3)^2\equiv 4^2 \equiv 16\equiv \\ &-1 \pmod{17}. \end{align} $$