1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ For CRT you need to use moduli $\,9,25,13,\,$ not $\,3,5,13\,$ $\endgroup$ – Bill Dubuque Apr 24 '15 at 19:13
  • $\begingroup$ 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? $\endgroup$ – Somebody Apr 24 '15 at 19:16
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Apr 24 '15 at 19:19
  • $\begingroup$ Okay I see & I'will try. Thank you ! $\endgroup$ – Somebody Apr 24 '15 at 19:23
  • $\begingroup$ Worked out perfectly, thank you :) $\endgroup$ – Somebody Apr 24 '15 at 19:44
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.