I have the calculation: $2^{31}\pmod {2925}$
It's for university and we should solve it like:
- make prime partition
- $2^{31}$ mod all prime partitions
- 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$
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.
Thanks to Bill Dubuque for the answer.