1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Solving large #s raised to a large # with the mod function

  1. Sep 7, 2007 #1
    1. The problem statement, all variables and given/known data

    Both of these questions are similar but the second is much larger so I thought I would post them both.

    1) 252^(611) mod 1207

    2) 8126^(3461) mod 8549

    2. Relevant equations

    Well, the most difficult part is that the numbers are so large you cannot just put it in the calculator.

    When you mod a number you are just looking for the remainder after you divide.

    3. The attempt at a solution

    First I tried just putting it in my calculator and my calculator responded with infinity as the answer, which is not correct.

    So I started thinking about what I know about mod's. I know my answer for the first question will be in the quantity 0<=ANSWER<=1206 and my second question will be 0<=ANSWER<=8548.

    So I tried to break up the exponent into smaller values such as 252^10 * 252^10 * ... but I realized that this would take really long and for my second question, that method would not be practical. So there has got to be someway to break the number down to a size the calculator can handle. Also the mod function by definition would be a great way to reduce that number if there was some way I could mod the number before taking the exponents when I break it down, but I'm not sure the rules and manipulates required to adjust the problem. There just has to be a better way to solve this type of a problem. Could you help? Thanks.
  2. jcsd
  3. Sep 7, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    If you just want to calculate them you can do it this way. Take your first example. Find
    252^2 mod 1207=740. Now to get 252^4 square 740 mod 1207.
    252^4 mod 1207=829. Now to get 252^8 square 829 mod 1207.
    252^8 mod 1207=458. Keep repeating
    252^16 mod 1207=953
    252^32 mod 1207=545
    252^64 mod 1207=103
    252^128 mod 1207=953
    252^256 mod 1207=545
    252^512 mod 1207=103

    Now 611=512+64+32+2+1. So you can just multiply the corresponding numbers from the table and reduce mod 1207. If you are clever, you can save even more time. Notice the 16 and 128 entries are the same. So 252^(128-16) mod 1207=1. Can you see how that would help?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook