What is the remainder when $40!$ is divided by $1763$?

Question

What is the remainder when $40!$ is divided by $1763$?

---

My try :

Factorizarion of $1763 = 41 * 43$

By using Wilson's theorem, I can say

$40! = -1 (mod 41) $

and $42.41.40! = -1(mod 43)$

=> $40! = -22(mod 43)$

---

How can I combine both the results ?

Answer 1

Letting $x=40!$, you have $$\begin{align} x&\equiv40\bmod41\\ x&\equiv21\bmod43 \end{align}$$ You can use the Chinese Remainder Theorem to solve this system of modulo equations.

Answer 2

We have $21\cdot41-20\cdot43=1$.

$40!=41q_1-1$ $\implies$ $(-20)\cdot43\cdot40!=-20\cdot1763q_1+20\cdot43=1763Q_1+860$

$40!=43q_2-22$ $\implies$ $21\cdot41\cdot40!=21\cdot1763q_2-21\cdot41\cdot22 = 21\cdot1763q_2-18942=1763Q_2+451$

Adding:

$(21\cdot41-20\cdot43)\cdot40!=1763(Q_1+Q_2)+860+451$

i.e. $40!\ =\ 1763Q+1311$

So the remainder is $1311$.

Answer 3

We have to solve the system of congruences: $\;\begin{cases}x\equiv \color{red}{-1}\mod 41,\\x\equiv\color{red}{21}\mod 43.\end{cases}$

Start from a Bézout's relation between $41$ and $43$: the extended Euclidean algorithm: $$\begin{array}{rrrr} r_i&u_i&v_i&q_i\\\hline 43&0&1\\41&1&0&1\\\hline 2&-1&1&20\\ 1&21&-20\\\hline \end{array}$$ yields the relation $\; 21\cdot41-20\cdot 43=1$.

Hence the solutions are $\;x\equiv \color{red}{21}\cdot21\cdot41-\color{red}{(-1)}\cdot20\cdot43\mod1763$. Reducing, one finds $$x=1311.$$

Answer 4

Basically the problem amounts to this: You have $x\equiv a\pmod m$, $x\equiv b\pmod n$, $\gcd(m,n)=1$, and you want to find the remainder when $x$ is divided by $mn$.

As $\gcd(m,n)$, there are integers $s,t$ such that $sm+tn=1$.

Multiplying $x=a+qm$ by $tn$ gives $$tnx\ =\ tna+tqmn\ \ldots\ \fbox1$$ Multiplying $x=b+rn$ by $sm$ gives $$smx\ =\ smb+srmn\ \ldots\ \fbox2$$ Adding $\fbox1$ and $\fbox2$ gives $$x\ =\ (tna+smb)+(tq+sr)mn$$ So the remainder is $tna+smb\pmod{mn}$.