# Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$.

I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$.

This was very long winded, I am sure there must be a shortcut. Can you help me find it?

• Hint :- 7!=1*2*3*4*5*6*7 = -28.-27.-26.-25.-24 .-23.-22 mod 29 and wilson states 28!=-1 mod 29 – Bswan Aug 27 '14 at 22:02

The big thing to realize here is that $7! = 7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1 \equiv -22 \cdot -23 \cdot -24\cdot-25\cdot-26\cdot-27 \cdot -28 \pmod{29}$.

So you have $(-1)^7 \cdot 28! \cdot 22 \cdot 23 \pmod{29}$ in total (notice I took out one of the two repeats of the $22$ and $23$ terms). You can then use Wilson's theorem to remove the factorial, and you're left with a simple multiplication.

• @OP The final multiplication is easier using the LHS of $\ 7\cdot 6\equiv (-22)(-23),\,$ i.e. we need only negate the factors $\,5,4,\ldots$ to complete $\,23!\,$ to $\,28!\ \$ – Gone Aug 27 '14 at 22:13

Hint $\$ Compute the product of all nonzero remainders mod $29$ in two ways, using two different complete systems of representatives, namely

$\qquad\qquad\! \color{#0a0}{{-}5,-4\ldots,-1},1,2,\ldots,23\qquad\qquad\quad\ \color{#0a0}{(-1)^5\, 5!}\: 23!$
$\qquad\quad\equiv\, 24,\,25\ldots,\ 28,1,2,\ldots,23\quad \overset{\rm product}\Rightarrow\ \ \equiv\, 28!\,\equiv\, {-}1\$ by Wilson's Theorem

Note $\$ 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.\,$ Your special case is the sequence $\, -k,\,-k\!+\!1,\ldots,-1,\require{cancel}\cancel{\color{#c00}0,} 1,2,\ldots, (p\!-\!k\!-\!1),\,$ with product $(-1)^k k!\, (p\!-\!k\!-\!1)!\equiv -1.\$ QED

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 "reflections")