Use the Chinese Reminder Theorem to find; (1030 ∗ 989) mod 3003.

chinese remainder theoremnumber theory

I have found a lot of help online for solving a system of congruences but I am not sure what to do with this?

I am having a lot of trouble with the Chinese Remainder Theorem in general, but this one is throwing me for a curve since it's not like most of the questions I have found online.

As stated:
Use the Chinese Reminder Theorem to find (1030 ∗ 989) mod 3003.

Any help is appreciated, thank you.

Best Answer

Call your unknown $x$. Going off the hint 3*1001=3003, you can rewrite your single congruence as:

\begin{align*} x &\equiv (1003)(989) \mod 3 \\ x &\equiv (1003)(989) \mod 1001 \end{align*} which, taking mods, simplifies to \begin{align*} x &\equiv (1)(2) \mod 3 \\ x &\equiv (2)(-12) \mod 1001 \end{align*}

Since $\mod 1001$ is still a bit unwieldy, you can repeat this process using $1001 = 7\cdot143$ and $143=11\cdot 13$ until you get a system of 4 congruences. Then apply CRT.

Related Question