1
$\begingroup$

Without using the fact that 2803 is prime, Calculate $2^{1401} \pmod{2803}$

Usually I would do something like:

$1401 = 3\times467$
$\equiv(2^{467})^3 \pmod{2803}$

And try to simplify it down and use the mod to get it down to something I can punch in the calculator, but in this case $2^{467}$ does not help as it is still too large.

If I did $(2^{3})^{467}$ that also does not seem to help as I just end up with $8^{467}$ and is too large

What other techniques can I use here?

1 Answers 1

1

Use exponentiation by squaring. It easily adapts to exponentiation with a modulus. You have the right idea by trying to factorize the exponent. All there is left to notice is that you do not need to factorize it, e.g., $1401 = 2 \cdot 700 + 1$ means you can compute $2^{700} \ (\text{mod} \ 2803)$, then square that and multiply by 2.

  • 0
    Ahh I understand, thanks heaps2012-09-26