CRT EulerFermatTheorem Difficult

Problem - 2739

Find the least non-negative residue of $70! \pmod{5183}$.


Answer     1277

Because $5183 = 71\times 73$, let's start by finding the residues of $70!$ mod $71$ and $73$.

By Wilson's theorem, $70! \equiv -1 \pmod{71}$.

Next, let $k = 70! \pmod{73}$. Then $71\times 72\times k \equiv 70!\times 71\times 72 \pmod{73} \implies (-2)(-1)k \equiv72! \pmod{73} \implies 2k \equiv -1 \pmod{73}$.

Note that $2\times 37 = 74 \equiv 1 \pmod{73}$. So $37\cdot 2k \equiv 37\cdot (-1) \pmod{73} \implies k \equiv -37 \equiv 36 \pmod{73}$.

Thus, $70!\equiv -1 \pmod{71}$ and $70!\equiv 36 \pmod{73}$.

Applying CRT to solve these two equations yields: $70! = \boxed{1277} \mod{5183}$.

report an error