Can anyone share me the trick to solve this problem using congruence?
Thanks,
Chan
Can anyone share me the trick to solve this problem using congruence?
Thanks,
Chan
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.)
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
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$...)
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}$