Chinese Remainder Theorem - solving a modulo with big numbers

The name of the pictureThe name of the pictureThe name of the pictureClash 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:



  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 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




share|cite|improve this question






















  • 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














up vote
1
down vote

favorite












I have the calculation: $2^31pmod 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 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




share|cite|improve this question






















  • 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












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:



  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 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




share|cite|improve this question














I have the calculation: $2^31pmod 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 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





share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Aug 20 at 12:30









JayTuma

1,333118




1,333118










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
















  • 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










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.






share|cite|improve this answer






















    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "69"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );








     

    draft saved


    draft discarded


















    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

















    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.






    share|cite|improve this answer


























      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.






      share|cite|improve this answer
























        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.






        share|cite|improve this 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.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Aug 20 at 12:25









        JayTuma

        1,333118




        1,333118










        answered Apr 24 '15 at 19:48









        Somebody

        1048




        1048






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            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
































































            -

            這個網誌中的熱門文章

            How to combine Bézier curves to a surface?

            圖片
            Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now. To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface? I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach? In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input. The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier curve. Additionally it marks one side of the curve as inside t
            閱讀完整內容

            Why am i infinitely getting the same tweet with the Twitter Search API?

            圖片
            up vote 0 down vote favorite My code workes perfectly for other queries, but for one query I am infinitely getting the same tweet. I can't understand what the problem is. API call: query='Allergic asthma OR Nonallergic asthma OR Occupational asthma OR EIB OR Exercise-induced bronchoconstriction OR Nocturnal asthma OR Cough-variant asthma' new_tweets = api.search(q=searchQuery, count=100, since_id=since_id, lang='en',tweet_mode='extended') if not new_tweets: print("No more tweets found") break for tweet in new_tweets: if True: print(jsonpickle.encode(tweet._json, unpicklable=False)) my_file = open('searchTweets.txt','a') my_file.write(jsonpickle.encode(tweet._json, unpicklable=False)+'n') my_file.close() else: continue Output in file: https://pastebin.com/JmRCsTeE These are the JSONs of the same Tweet. Other queries that work: Breast cancer OR Prostate cancer OR Colon cancer OR Lung cancer Type 2 dia
            閱讀完整內容

            Is there any way to eliminate the singular point to solve this integral by hand or by approximations?

            圖片
            Clash Royale CLAN TAG #URR8PPP up vote 0 down vote favorite 1 $$int_0^1 (1+(x^-p-1)^1-p)^frac1pdx, pin mathbbR, pge 1$$ I find that $x=0,1$ are singular points(discontinuous points of this integral), is there a way to eliminate those singular points to make sure that this integral can be calculated by hand or by Taylor approximations. In either cases, what are those steps of calculating the integral? calculus real-analysis analysis approximation share | cite | improve this question edited Sep 11 at 5:07 asked Sep 11 at 4:48 Mclalalala 126 8 1 What is $p$? Please give more information to make it complete. – xbh Sep 11 at 5:02 @xbh already fixed it, thanks for reminding. – Mclalalala Sep 11 at 5:10 Seems that $0$ is not singular here… [I might compute wrong] – xbh Sep 11 at 5:30 @xbh can you show me how to get the close formula for the integral above? – Mclalalala Sep 11 at 5:33
            閱讀完整內容