Friday, December 2, 2016

elementary number theory - What is the remainder of $18!$ divided by $437$?





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.


Answer




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$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...