Factorials and Mod
What is $((69)!)^2 \mod 73$? How do I solve this problem? Is there a theorem which would help me solve this? This is just one of the "easy" questions in my probset, but I don't know how to solve.
Hint $ $ By Wilson, $\rm\ mod\ p\!:\: -1 \equiv (p\!-\!1)! = (p\!-\!1)(p\!-\!2)(p\!-\!3)(p\!-\!4)! \equiv (-1)(-2)(-3)(p-4)!$
But by prime $\rm\:p \ne 2,3,\: \ \ 2\cdot 3 = 6\:$ will be invertible mod $\rm\:p,\:$ so $\rm\:(p\!-\!4)! \equiv 1/6\pmod p$
Furthermore: $\rm\ \ p = 6\:k\pm 1\:\Rightarrow\:(p-4)! \equiv 1/6 \equiv (1\mp p)/6\equiv \mp k$
Note $\:$ The signed-equation denotes two equations: the top sign case, and bottom sign case. $$\begin{eqnarray}\rm\:p = 6\:\!k{\color{#C00}{+1}}\: &\Rightarrow& \rm\:(p-4)!\equiv 1/6\equiv (1+{\color{#C00}{(-1)}} p)/6\equiv -k&\rm\quad top\ signs \\ \rm\:p = 6\:\!k{\color{#C00}{-1}}\: &\Rightarrow &\rm\:(p-4)!\equiv 1/6\equiv (1+{\color{#C00}{(+1)}} p)/6\equiv\ k&\rm\quad bottom\ signs \end{eqnarray}$$
Indeed, we seek $\rm\:x\:$ so $\rm\:6\:|\:1+x\:\!p,\:$ or $\rm\:mod\ 6\!:\: -1\equiv x\:\!p \equiv x\!\:s,\:$ where $\rm\:\color{#C00}s = (p\ mod\ 6).\:$ Therefore $\rm\:x \equiv -1/s.\:$ Here $\rm\:s\equiv \pm1\:\Rightarrow\:s^2 = 1\:\Rightarrow\: x \equiv -1/s = -s/s^2 = -s.\:$ Therefore $$\rm\:p = 6\:\!k+{\color{#C00}{s}}\: \Rightarrow\: (p-4)!\equiv 1/6\equiv (1+{\color{#C00}{(-s)}}\:\! p)/6\equiv \color{#C00}{-s}\,k\quad abstract\ sign$$
where the last congruence is obtained as follows: $\rm\:1 - s\,p \equiv s(s\!-\!p) \equiv s(-6k).$
Hence the equation that I wrote above involving the signs $\pm$ and $\mp,$ denotes two equations, the case $\rm\:s = 1\:$ of above (choose all the top signs) and case $\rm\:s = -1\:$ (choose all the bottom signs). Indeed, if we substitute $\rm\: s = \pm 1\:$ then $\rm -s = \mp 1,\:$ so we obtain said equation with signs.
Hint: Use Wilson's theorem to note that $69!\cdot 70\cdot 71\cdot 72\equiv -1 \pmod {73}$. Solve for $69!\pmod {73}$