2
$\begingroup$

This was a question on my exam which I could not answer at that time (it was about 3 years ago). However, I think I have the solution now.

The prime decomposition of $2014 = 2 \cdot 19 \cdot 53$. Therefore $50! \mod 2014$ results in the following system of congruences: $$\begin{cases} 50! \equiv 0 \mod 2\\ 50! \equiv 0 \mod 19\\ 50! \equiv 50! \mod 53 \end{cases}$$ This is equivalent with $$\begin{cases} 50! \equiv 0 \mod 38\\ 50! \equiv 50! \mod 53 \end{cases}.$$

Because of Wilson's congruence, we know that $52! \equiv -1 \mod 53$. Note that $52 \cdot 51 \equiv (-1) \cdot (-2) \equiv 2 \mod 53$. Hence $2 \cdot 50! \equiv -1 \mod 53$. Mulitplying both sides with $-26$, we find that $50! \equiv 26 \mod 53$. The resulting system of congruences is $$\begin{cases} 50! \equiv 0 \mod 38\\ 50! \equiv 26 \mod 53 \end{cases}.$$

Now the inverse of $38 \mod 53$ is $7$, so we find that $26 \cdot 38 \cdot 7 = 6916$ satisfies both equations in the system of congruences. Can I conclude from the Chinese Remainder Theorem that $50! \equiv 6916 \equiv 874 \mod 2014$?

$\endgroup$
  • $\begingroup$ i have also $$50!\equiv 874 \mod 2014$$ $\endgroup$ – Dr. Sonnhard Graubner Feb 18 '17 at 16:53
  • $\begingroup$ So I could make this conclusion using the Chinese Remainder Theorem? Because the system of congruences gives that $53$ divides $50! - 26$ and $38$ divides $50!$, so I would add multiples of $53$ in the first case and multiples of $38$ in the second case in order to find something like $53$ divides $n$, $38$ divides $n$ and hence $2014$ divides $n$, but this would be quite long to compute I guess... $\endgroup$ – Student Feb 18 '17 at 16:55
1
$\begingroup$

Yes, your proof looks correct.

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