# Thread: how do i find 5^2003 (mod1001) by using Chinese Remainder theorem?

1. ## how do i find 5^2003 (mod1001) by using Chinese Remainder theorem?

Yeah i know these:

5^2003=3 mod7
5^2003=4 mod11
5^2003=8 mod13

and 1001=7x11x13

but i couldnt find that 5^2003=y(mod1001)

can anyone express clearly how to conclude this problem by using chinese remainder theorem?

2. Originally Posted by eyke
Yeah i know these:

5^2003=3 mod7
5^2003=4 mod11
5^2003=8 mod13

and 1001=7x11x13

but i couldnt find that 5^2003=y(mod1001)

can anyone express clearly how to conclude this problem by using chinese remainder theorem?

I get answer 125 by Euler's Theorem.
5^2003 = 5^(1000*2+3) = [5^(1000*2)][5^3]
5 and 1001 are relative primes
by Euler's Theorem, we know 5^1000 = 1 (mod 1001)
[5^(1000*2)][5^3] (mod 1001) = 1 * 5^3 (mod 1001) =125

3. Originally Posted by eyke
Yeah i know these:

5^2003=3 mod7
5^2003=4 mod11
5^2003=8 mod13
You have: $\displaystyle x\equiv 3(\bmod 7),x\equiv 4(\bmod 11),x\equiv 8(\bmod 13)$. The congruences can be written as $\displaystyle x\equiv 3 - 7\cdot 3(\bmod 7)$, $\displaystyle x\equiv 4 - 2\cdot 11 (\bmod 11)$. This gives $\displaystyle x\equiv -18(\bmod 7)$ and $\displaystyle x\equiv -18(\bmod 11)$, this combines into $\displaystyle x\equiv -18(\bmod 77)$. We can write, $\displaystyle x\equiv - 18 - (77)(26) (\bmod 77)$ and $\displaystyle x\equiv 8 - (13)(156)(\bmod 13)$. Therefore, $\displaystyle x\equiv -2020 \equiv 983(\bmod 1001)$

4. Originally Posted by ThePerfectHacker
You have: $\displaystyle x\equiv 3(\bmod 7),x\equiv 4(\bmod 11),x\equiv 8(\bmod 13)$. The congruences can be written as $\displaystyle x\equiv 3 - 7\cdot 3(\bmod 7)$, $\displaystyle x\equiv 4 - 2\cdot 11 (\bmod 11)$. This gives $\displaystyle x\equiv -18(\bmod 7)$ and $\displaystyle x\equiv -18(\bmod 11)$, this combines into $\displaystyle x\equiv -18(\bmod 77)$. We can write, $\displaystyle x\equiv - 18 - (77)(26) (\bmod 77)$ and $\displaystyle x\equiv 8 - (13)(156)(\bmod 13)$. Therefore, $\displaystyle x\equiv -2020 \equiv 983(\bmod 1001)$