Chinese Remainder Theorem - solving a modulo with big numbers
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I have the calculation: $2^31pmod 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 pmod3$$
$$2^31 equiv 3 pmod5$$
$$2^31 equiv 11 pmod13$$
I made:
$$x equiv 2 pmod3$$
$$x equiv 3 pmod5$$
$$x equiv 11 pmod13$$
Then I tried CRT and got $x = -1237 + 195k$
If you simply calculate $2^31pmod 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!
chinese-remainder-theorem
edited Aug 20 at 12:30
JayTuma
1,333118
asked Apr 24 '15 at 19:02
Somebody
1048
 |Â
show 2 more comments
up vote
1
down vote
favorite
I have the calculation: $2^31pmod 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 pmod3$$
$$2^31 equiv 3 pmod5$$
$$2^31 equiv 11 pmod13$$
I made:
$$x equiv 2 pmod3$$
$$x equiv 3 pmod5$$
$$x equiv 11 pmod13$$
Then I tried CRT and got $x = -1237 + 195k$
If you simply calculate $2^31pmod 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!
chinese-remainder-theorem
edited Aug 20 at 12:30
JayTuma
1,333118
asked Apr 24 '15 at 19:02
Somebody
1048
For CRT you need to use moduli $,9,25,13,,$ not $,3,5,13,$
– Number
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?
– Somebody
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.
– Number
Apr 24 '15 at 19:19
Okay I see & I'will try. Thank you !
– Somebody
Apr 24 '15 at 19:23
Worked out perfectly, thank you :)
– Somebody
Apr 24 '15 at 19:44
 |Â
show 2 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have the calculation: $2^31pmod 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 pmod3$$
$$2^31 equiv 3 pmod5$$
$$2^31 equiv 11 pmod13$$
I made:
$$x equiv 2 pmod3$$
$$x equiv 3 pmod5$$
$$x equiv 11 pmod13$$
Then I tried CRT and got $x = -1237 + 195k$
If you simply calculate $2^31pmod 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!
chinese-remainder-theorem
edited Aug 20 at 12:30
JayTuma
1,333118
asked Apr 24 '15 at 19:02
Somebody
1048
I have the calculation: $2^31pmod 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 pmod3$$
$$2^31 equiv 3 pmod5$$
$$2^31 equiv 11 pmod13$$
I made:
$$x equiv 2 pmod3$$
$$x equiv 3 pmod5$$
$$x equiv 11 pmod13$$
Then I tried CRT and got $x = -1237 + 195k$
If you simply calculate $2^31pmod 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!
chinese-remainder-theorem
edited Aug 20 at 12:30
JayTuma
1,333118
asked Apr 24 '15 at 19:02
Somebody
1048
edited Aug 20 at 12:30
JayTuma
1,333118
edited Aug 20 at 12:30
JayTuma
1,333118
edited Aug 20 at 12:30
JayTuma
1,333118
1,333118
asked Apr 24 '15 at 19:02
Somebody
1048
asked Apr 24 '15 at 19:02
Somebody
1048
asked Apr 24 '15 at 19:02
Somebody
1048
1048
For CRT you need to use moduli $,9,25,13,,$ not $,3,5,13,$
– Number
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?
– Somebody
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.
– Number
Apr 24 '15 at 19:19
Okay I see & I'will try. Thank you !
– Somebody
Apr 24 '15 at 19:23
Worked out perfectly, thank you :)
– Somebody
Apr 24 '15 at 19:44
 |Â
show 2 more comments
For CRT you need to use moduli $,9,25,13,,$ not $,3,5,13,$
– Number
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?
– Somebody
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.
– Number
Apr 24 '15 at 19:19
Okay I see & I'will try. Thank you !
– Somebody
Apr 24 '15 at 19:23
Worked out perfectly, thank you :)
– Somebody
Apr 24 '15 at 19:44
For CRT you need to use moduli $,9,25,13,,$ not $,3,5,13,$
– Number
Apr 24 '15 at 19:13
For CRT you need to use moduli $,9,25,13,,$ not $,3,5,13,$
– Number
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?
– Somebody
Apr 24 '15 at 19:16
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?
– Somebody
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.
– Number
Apr 24 '15 at 19:19
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.
– Number
Apr 24 '15 at 19:19
Okay I see & I'will try. Thank you !
– Somebody
Apr 24 '15 at 19:23
Okay I see & I'will try. Thank you !
– Somebody
Apr 24 '15 at 19:23
Worked out perfectly, thank you :)
– Somebody
Apr 24 '15 at 19:44
Worked out perfectly, thank you :)
– Somebody
Apr 24 '15 at 19:44
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
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.
edited Aug 20 at 12:25
JayTuma
1,333118
answered Apr 24 '15 at 19:48
Somebody
1048
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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.
edited Aug 20 at 12:25
JayTuma
1,333118
answered Apr 24 '15 at 19:48
Somebody
1048
add a comment |Â
up vote
0
down vote
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.
edited Aug 20 at 12:25
JayTuma
1,333118
answered Apr 24 '15 at 19:48
Somebody
1048
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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.
edited Aug 20 at 12:25
JayTuma
1,333118
answered Apr 24 '15 at 19:48
Somebody
1048
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.
edited Aug 20 at 12:25
JayTuma
1,333118
answered Apr 24 '15 at 19:48
Somebody
1048
edited Aug 20 at 12:25
JayTuma
1,333118
edited Aug 20 at 12:25
JayTuma
1,333118
edited Aug 20 at 12:25
JayTuma
1,333118
1,333118
answered Apr 24 '15 at 19:48
Somebody
1048
answered Apr 24 '15 at 19:48
Somebody
1048
answered Apr 24 '15 at 19:48
Somebody
1048
1048
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1250316%2fchinese-remainder-theorem-solving-a-modulo-with-big-numbers%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
For CRT you need to use moduli $,9,25,13,,$ not $,3,5,13,$
– Number
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?
– Somebody
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.
– Number
Apr 24 '15 at 19:19
Okay I see & I'will try. Thank you !
– Somebody
Apr 24 '15 at 19:23
Worked out perfectly, thank you :)
– Somebody
Apr 24 '15 at 19:44