3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$

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