Can anyone share me the trick to solve this problem using congruence?
Thanks,
Chan
4 Answers
$\begingroup$If you've seen Wilson's theorem then you know the remainder when $18!$ is divided by $19$. To get $16!$ mod $19$, then, you can multiply by the multiplicative inverses of $17$ and $18$ mod $19$. Do you know how to find these? (Edit: Referring to both inverses might be a bit misleading, because you really only need to invert their product. See also Bill Dubuque's answer.)
$\endgroup$ 4 $\begingroup$Hint $ $ By Wilson's theorem $\bmod 19\!:\ \overbrace{{-}1}^{\large \color{#0a0}{18}} \equiv 18! \equiv\!\! \overbrace{18\cdot17}^{\large \color{#c00}{(-1)(-2)}}\!\!\cdot 16!\,$ $\Rightarrow\,16!\equiv \dfrac{\color{#0a0}{18}}{\color{#c00}2}\equiv 9$
Generally (Wilson reflection formula) $\rm\displaystyle\ (p\!-\!1\!-\!k)!\equiv\frac{(-1)^{k+1}}{k!}\!\!\!\pmod{\!p},\,$ $\rm\:p\:$ prime
$\endgroup$ 8 $\begingroup$I almost think in this case it is just faster to break it down than calculate the inverses: First the factors between 1 and 10:
$$10!= (2\cdot 10)\cdot (4\cdot5)\cdot(3\cdot6)\cdot(7\cdot8)\cdot 9\equiv 1\cdot 1\cdot (-1)\cdot(-1)\cdot 9\equiv9$$
Now we have
$$16!\equiv 9\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\equiv9\cdot(-8)\cdot(-7)\cdot(-6)\cdot(-5)\cdot(-4)\cdot(-3)$$
$$\equiv 9\cdot(4\cdot5)\cdot(6\cdot3)\cdot(7\cdot8)\equiv 9\cdot(1)\cdot(-1)\cdot(-1)\equiv 9$$
Of course this doesn't generalize, but the computation is faster than finding 3 inverses and multiplying them. (Again of course that is not true for larger $n$...)
$\endgroup$ $\begingroup$A more explicit answer would go like this:
By Wilson's Theorem, $18!$ is congruent to $-1 \pmod {19}$
$$18! = (18\cdot 17)(16!)$$
Then $(18\cdot 17)(16!)$ is congruent to $-1 \pmod{19}$
But note that $18$ is congruent to $-1 \pmod{19}$ and $17$ is congruent to $-2 \pmod{19}$
Then it follows that $(18\cdot 17)(16!)$ is congruent to $((-1)\cdot (-2))(16!)$ is congruent to $-1 \pmod{19}$
Simplifying, we get, $2\cdot(16!)$ is congruent to $-1 \pmod{19}$. But we need the remainder of $16!$, not $2\cdot 16!$. and $-\frac12$ isn't a valid answer.
Then also notice that $18$ is congruent to $-1 \pmod{19}$. Then $2\cdot 16!$ is congruent to $18 \pmod{19}$ by the fact that if $a$ is congruent to $b \pmod{p}$, then $b$ is congruent to $a \pmod{p}$
So we have that $2\cdot 16!$ is congruent to $18 \pmod{19}$ and from there, its just a matter of dividing both sides by $2$ to get $16!$ is congruent to $9 \pmod{19}$
$\endgroup$
