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