Modular Arithmetic – How to Calculate Modulo of a High-Raised Number

exponentiationmodular arithmetic

I need some help with this problem:

$$439^{233} \mod 713$$

I can't calculate $439^{223}$ since it's a very big number, there must be a way to do this.

Thanks.

Best Answer

There are often tricks to this if the numbers are nice enough, but even if they're not, here's a way that's not entirely horrible.

You already know what 439 is mod 713. What is $439^2 \mod 713$? What about $439^4$? (Hint: take your answer for $439^2$ after reducing it mod 713, and then square it again.) In the same way, calculate $439^8, 439^{16}, \dots, 439^{128} \mod 713$. Now just note that 233 = 128 + 64 + 32 + 8 + 1. So multiply the appropriate powers of 439 together - again, one calculation at a time, reducing mod 713 each time.

Now you should only have to do 11 calculations, and now all your numbers are 6 digits or less. Rather than impossible, it's now simply tedious. :)

By the way, one thing to notice: 713 = 23 * 31. Perhaps your calculations will be easier if you do them mod 23 and 31, then apply the Chinese remainder theorem?

Related Question