[Math] Chinese Remainder Theorem – solving a modulo with big numbers

chinese remainder theorem

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!

Best Answer

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.

Related Question