3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Bswan Aug 27 '14 at 22:02
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @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!\ \ $ $\endgroup$ – Gone Aug 27 '14 at 22:13
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.