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

[Fresh4Christ]

Homework Statement

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

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

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.

 

[Dick]

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?