Chinese Remainder Theorem, discrete math problem

Question

$5^{2003}$ $\equiv$ $ 3 \pmod 7 $

$5^{2003}$ $\equiv$ $ 4\pmod{11}$

$5^{2003} \equiv 8 \pmod{13}$

Solve for $5^{2003}$ $\pmod{1001}$ (Using Chinese remainder theorem).

Answer 1

Interesting question! First of all let's check some things on how to depict the solution.

Chinese Remainder Theorem

If $m_{1},m_{2}, \cdots, m_{k}$ are positive integers with $(m_{i},m_{j}) = 1$ for any $1 \le i < j \le k$, then the system

\begin{align} x & \equiv b_{1} \pmod{m_{1}} \\ x & \equiv b_{2} \pmod{m_{2}} \\ &\; \; \vdots \notag \\ x & \equiv b_{k} \pmod{m_{k}} \end{align} must have solutions for any integers $ b_{1},b_{2}, \cdots, b_{k}$ and the solution set is a congruence class modulo $m_{1},m_{2}, \cdots, m_{k}$ that is, the solutions are formed by the numbers

$ x \equiv M_{1}M_{1}^{-1}b_{1} + M_{2}M_{2}^{-1}b_{2}+ \cdots + M_{k}M_{k}^{-1}b_{k} \pmod{m_{1},m_{2}, \cdots, m_{k}}$

Where $M_{i} = \frac{m_{1},m_{2}, \cdots, m_{k}}{m_{i}}$ and $ M_{i}^{-1}$ is the inverse of $M_{i}$ modulo $m_{i}$ for $i = 1, 2, \cdots, k.$

Now you just have to recall that the inverse is any solution of the equation $ax \equiv 1 \pmod{m} $ that has solutions if and only if $ (a,m) = 1$.

With that being said let´s take $x = 5^{2003}$ and our system will be:

$x \equiv 3 \pmod{7}$

$x \equiv 4 \pmod{11}$

$x \equiv 8 \pmod{13}$

Then, clearly the systmem holds the conditions of the theorem. Knowing that $ 11 \cdot 7 \cdot 13 = 1001 $ and after some calculations, we'll get: \begin{align} M_{1} = \frac{1001}{7} = 143 & ; M_{1}^{-1} = 5 \\ M_{2} = \frac{1001}{11} = 91 & ; M_{2}^{-1} = 4 \\ M_{3} = \frac{1001}{13} = 77 & ; M_{3}^{-1} = 12 \end{align}

Therefore by CRT

$ x \equiv 143\cdot 5 \cdot 3 + 91\cdot 4 \cdot 4 + 77\cdot 12 \cdot 8 \pmod{1001} $

$ x \equiv 10,993 \equiv 983 \pmod{1001} $

The answer is $983.$

Answer 2

Since we are given information about $5^{2003}$ and then asked to find $5^{2003}$, I would start by letting $x= 5^{2003}$.

x= 3 mod 7 so x= 7i+ 3. x= 4 mod 11 so x= 11j+ 4.

7i+ 3= 11j+ 4 7i- 11j= 1 7 divides into 11 once with remainder 4; 11- 7= 4. 4 divides into 7 once with remainder 3; 7- 4= 3 so 7- (11- 7)= 2(7)- 11= 3. 3 divides into 4 once with remainder 1; 4- 3= 1 so (11- 7)- (2(7)- 11)= 2(11)- 3(7)= 1.

i= -3+ 11m and j= -2+ 7m for some m. Replacing m with n+ 1, i= -3+ 11n+ 11= 8+ 11n and j= -2+ 7n+ 7= 5+ 7n. Check: 7i- 11j= 7(8+ 11n)- 11(5+ 7n)= 56+ 77n- 55- 77n= 1.

x= 7i+ 3= 56+ 77n+ 3= 59+ 77n.

We also have x= 8 mod 13 so x= 13k+ 8. 59+ 77n= 13k+ 8. 13k- 77n= 51.

13 divides into 77 5 times with remainder 12: 77- 5(13)= 12 12 divides into 13 once with remainder 1: 13- 12= 1.

13- 12= 13- (77- 5(13)= 6(13)- 77= 1 Multiply by 51: 306(13)- 51(77)= 51.

So k= 306+ 77m and n= 51+ 13m. Check 13k- 77n= 3978+ 1001m- (3927+ 1001m)= 51.

So x= 59+ 77n= 59+ 77(51+ 13m)= 59+ 3927+ 1001n= 3986+ 1001n.

x= $5^{2003}$= 3986= 983 (mod 1001).

Check: 983/7= 140 with remainder 3: 987= 3 (mod 7). 983/11= 89 with remainder 4: 987= 4 (mod 11). 983/13= 75 with remainder 8: 986= 8 (mod 13).