Register to reply 
Solving large #s raised to a large # with the mod function 
Share this thread: 
#1
Sep707, 11:15 AM

P: 10

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. Solve: 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
Sep707, 05:02 PM

Sci Advisor
HW Helper
Thanks
P: 25,228

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^(12816) mod 1207=1. Can you see how that would help? 


Register to reply 
Related Discussions  
Large LED's  Electrical Engineering  6  
Large leyden jar help?  General Physics  1  
Large intergral  Calculus  2  
Is ln(1+exp(x)) = x when x is a large number?  General Math  11  
How large is this  General Discussion  7 