$\begingroup$

What is the remainder of $18!$ divided by $437$?

I'm getting a little confused in the solution. It uses Wilson's theorem

Wilson's Theorem:
If $p$ is prime then $(p-1)!\equiv-1(\text{mod } p)$

So it first factors $437$ into primes. So $437 = 19 \cdot 23$. Then from Wilson's theorem notes that $18!\equiv-1(\text{mod } 19)$ so we're part way there, but also says $22\equiv22!(\text{mod }23)$ by Wilson's theorem (really don't know how they got this from $22!\equiv-1(\text{mod }23)$.

Also I'm confused how solving this leads to finding the remainder for $18!$ divided by $437$? I understand getting $18!$ from $19$ but not the $23$ part.

$\endgroup$ 3

3 Answers

$\begingroup$

By Wilson's theorem, $18!\equiv-1\mod 19$ and $22!\equiv-1\mod 23$. Now

$22!=22\times21\times20\times19\times18!\equiv(-1)(-2)(-3)(-4)18!\equiv(24)18!\equiv(1)18!=18!\mod 23.$

Therefore $18!\equiv-1\mod19$ and $18!\equiv-1\mod 23$.

By the constant case of the Chinese remainder theorem, therefore,

$18! \equiv-1\equiv436\mod 437=19\times23$.

$\endgroup$ $\begingroup$

$$\begin{align}22!&\equiv22\cdot21\cdot20\cdot19\cdot18!\\ &\equiv(-1)(-2)(-3)(-4)18!\\ &\equiv24\cdot18!\equiv18!\pmod{23} \end{align}$$

Can you take it from here?

$\endgroup$ $\begingroup$

We know we can get the solution from the Chinese remainder Theorem

If $18! \equiv a \pmod {19}$ and $18!\equiv b \pmod{23}$ we'll be able to solve $18! \equiv x\pmod{19*23}$.

And by wilson's theorem $19!\equiv -1\pmod{19}$. So we know $a$.

And by wilson's theorem $22! \equiv -1 \pmod{23}$

And $22! = 18!*(19*20*21*22)\equiv 18!*(-4*(-3)*(-2)*(-1))\equiv 18!*24 \equiv 18! \pmod {23}$.

And that's the gyst.... $18!\equiv 18!*24\equiv 18!4!\equiv 18!(22*21*20*19)\equiv 22!\equiv-1\pmod {23}$.

So we have $18! \equiv -1\pmod {19}$ and $18!\equiv -1 \pmod {23}$ and so by CRT $18! \equiv -1 \equiv 436 \pmod{437}$.

$\endgroup$