How do you compute 4948^41 (mod 5963)? I tried to reduce the exponent to 32+8+1. However, I get stuck with the calculations and end up getting numbers that cannot fit in the calculator. Please help.
Asked
Active
Viewed 65 times
2 Answers
0
Use some compute algebra system. In Maple, 4948^41 mod 5963 returns 4401 in 4 secs (probably less, I did not time it).
Sergio Parreiras
- 3,813
-
wait so 4401 is the answer that appeared in 4 seconds? – Ellen Dec 11 '13 at 05:15
-
yes 4401 is the answer – Sergio Parreiras Dec 11 '13 at 05:20
-
My professor says that 4401 is the wrong answer. So now I'm still lost – Ellen Dec 11 '13 at 13:02
-
Alpha, http://m.wolframalpha.com/ gives the same answer as Maple, 4401, the command is Mod[x,y] to get x mod y. Try the calculator suggestion of the chosen answer to prove your professor wrong. – Sergio Parreiras Dec 11 '13 at 13:46
0
Using a calculator, your approach is fine. Start by squaring $4948^2=24482704 \equiv 4589 \pmod {5963}$ That fits in an eight digit calculator. Each square is reduced $\pmod {5963}$, so never exceeds eight digits. Then multiplying up to get the $41$ power again fits, as long as you reduce each step along the way. It is true, if you use a computer algebra system, you don't have to worry about that. Alpha gets it in less than 4 seconds as well.
Ross Millikan
- 374,822
-
According to Alpha the answer is 4401. However my professor said that answer is wrong. So I'm still lost – Ellen Dec 11 '13 at 13:01