# Chinese Remainder Theorem - solving a modulo with big numbers

I have the calculation: $2^{31}\pmod {2925}$

It's for university and we should solve it like:

1. make prime partition
2. $2^{31}$ mod all prime partitions
3. Solve with Chinese Remainder Theorem.

I started with $2925 = 3 \cdot 3 \cdot 5 \cdot 5 \cdot 13$ , and found out that: $$2^{31} \equiv 2 \pmod{3}$$ $$2^{31} \equiv 3 \pmod{5}$$ $$2^{31} \equiv 11 \pmod{13}$$ I made: $$x \equiv 2 \pmod3$$ $$x \equiv 3 \pmod5$$ $$x \equiv 11 \pmod{13}$$

Then I tried CRT and got $x = -1237 + 195k$

If you simply calculate $2^{31}\pmod{ 2925}$ you get $1298$, which is in fact $-1237 + 195 \cdot 13$.

I don't know how to find out the $13$.

Any help appreciated.

EDIT:

SOLVED! I took $3$ instead of $9$ and $5$ instead of $25$ after prime partition. For more infos please see comments. Thanks!

• For CRT you need to use moduli $\,9,25,13,\,$ not $\,3,5,13\,$ Apr 24 '15 at 19:13
• Ah, so I need to multiply the same primes.. like if I had 3*3*3 instead of 3*3 I had to take 27? Apr 24 '15 at 19:16
• You want the lcm of the moduli to be $2925$ in order to get the result mod $2925$, and you want them pairwise coprime so you can apply CRT. Apr 24 '15 at 19:19
• Okay I see & I'will try. Thank you ! Apr 24 '15 at 19:23
• Worked out perfectly, thank you :) Apr 24 '15 at 19:44

For CRT you need to use moduli $9,25,13$ not $3,5,13$
You want the l.c.m. of the moduli to be $2925$ in order to get the result modulo $2925$, and you want them pairwise coprime so you can apply CRT.