Register to reply

Solving large #s raised to a large # with the mod function

by Fresh4Christ
Tags: function, raised, solving
Share this thread:
Fresh4Christ
#1
Sep7-07, 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.
Phys.Org News Partner Science news on Phys.org
Flapping baby birds give clues to origin of flight
Prions can trigger 'stuck' wine fermentations, researchers find
Socially-assistive robots help kids with autism learn by providing personalized prompts
Dick
#2
Sep7-07, 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^(128-16) 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