Least positive residue of $10! \pmod {143}$

Question

So I got that $10! \equiv 10 \pmod {11}$ and $10! \equiv 9 \pmod{13}$ but I am not sure how to apply the chinese remainder theorem to arrive at the solution for $x \equiv 10!\pmod {143}$ Thanks.

Answer 1

There are various ways to implement CRT, here is one: let $x=10!$ and set $$x=11a+13b\ .$$ Reducing modulo $11$ and using the fact that $x\equiv10\pmod{11}$ gives $$2b\equiv10\pmod{11}$$ so $b=5$ is a possible solution. Doing something similar modulo $13$ gives a possible $a=-3$. So one possible $x$ is $11\times(-3)+13\times5=32$. The CRT guarantees that there will be a unique solution modulo $143$, so the complete solution is $$x\equiv32\pmod{143}\ .$$ The least positive residue is $32$.

Addendum. . . and probably the easiest way to evaluate $10!$ modulo $13$ is $$\eqalign{10! &\equiv1\times(2\times7)\times(3\times9)\times(4\times10)\times(5\times8)\times6\cr &\equiv1\times1\times1\times1\times1\times6\cr &\equiv6\ .\cr}$$

Answer 2

You need a number satisfying $x\equiv 10 \pmod {11}$ and $x\equiv 9 \pmod {13}$.

The easiest way to find this, since the numbers aren't so big, is to start with $10$, and then add $11$ to it as many times as it takes to find a number satisfying the second congruence. Thus: $10, 21, 32, 43, 54, 65, 76, 87$.

The Chinese Remainder Theorem proof gives a different way. First, we note that, modulo $13$, we have $11^{-1}=6$, while modulo $11$, we have $13^{-1}=6$. Therefore we construct our solution:

$x\equiv 11\cdot 6\cdot 9 + 13\cdot 6\cdot 10 \pmod {143}$

$x\equiv 660+702 = 1374 \equiv 87 \pmod {143}$

Answer 3

All of the answers posted here are incorrect.

$143 = 11 \cdot 13$

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

Similarly, $12! \equiv -1 \pmod {13}$ so $10! \equiv -(11 \cdot 12)^{-1} \equiv -7 \equiv 6 \pmod {13}$

Solving this system gives $32$.

Answer 4

With the correction $\,x := 10!\equiv 6\pmod{13}\,$ we have more generally for odd $\,m\,$

$$\!\!\begin{eqnarray} {\rm mod}\ m\!: &&x\equiv a&&\iff x\equiv a+2m\\ {\rm mod}\ m\!+\!2\!: &&x\equiv a\!-\!4\!\!&&\iff x\equiv a+2m\end{eqnarray}\!\iff\! x\equiv a + 2m\!\pmod{m(m\!+\!2)}$$

Therefore for $\ a,m = 10,11\,$ we obtain $\,x\equiv a+2m\equiv 10+2(11)\equiv 32\pmod{11\cdot 13}$