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

Need some assistance on answering this problem. For this question, there is no answer at the back of Kenneth Rosen’s book. I initially began tackling this problem using Wilson’s theorem, where

$40! \equiv -1$ (mod $41$)

$1763 = 41 * 43$

gcd($41,43$) $= 1$, hence these two numbers are relative primes.

$42! \equiv -1$ (mod $43$) $\Rightarrow 42! = 40! * 41 * 42 = 40! * 2 \equiv -1$ (mod $43$).

Using Euler’s phi-function to find the inverse I obtained,

$40! \equiv -1 * 2^{41}$ (mod $43$) $\equiv -22$ (mod $43$). Thus,

$40! \equiv 22$ mod $1763$). Have I done this correctly? If not, can you correct me and explain my mistakes.

Solutions Collecting From Web of "What is the remainder when $40!$ is divided by $1763$?"

You have calculated $40!$ modulo 41 and 43 correctly, but mere multiplication of the residues to get the final answer is not correct.
$$40!\equiv-1\bmod41$$
$$40!\equiv-22\bmod43$$
$$40!\not\equiv22\bmod1763$$
Combining the moduli is an instance of the Chinese remainder theorem, and any method to solve such a linear system of congruences will yield
$$40!\equiv1311\bmod1763$$
I leave the details of getting 1311 out, because here trial and error (starting with $-22$ and adding 43 until the number is $\equiv-1\bmod41$) is feasible.

You cannot conclude that $40! \equiv -1\times -22 \pmod{1763}$

You need to find :

  • $x_1$ such that $x_1 \equiv 1 \pmod{41}$ and $x_1 \equiv 0 \pmod{43}$
  • $x_2$ such that $x_2 \equiv 0 \pmod{41}$ and $x_2 \equiv 1 \pmod{43}$

Then $40! \equiv -x_1 -22x_2 \pmod{41\times43}$

For instance $x_1 = 21 \times 43\equiv 903 \pmod{1763}$ and $x_2 = -22 \times 41 \equiv 861 \pmod{1763}$ therefore $40! \equiv -903-22\times 861 \equiv 1311 \pmod{1763}$