How do I simplify the following:
$a^{b} \ \pmod {b}$ where $b$ is very large.
For example:
$2^{499} \pmod {999}$
How do I find the result without computing all?
I don't want to use such a quantity of memory for storing the value of $2^{499}$.
Is there any sort of property to find the result in a faster way?
Note that $999=27\times 37$
Now Fermat-Euler Theorem tells us that $2^{18}\equiv 1 \bmod 27$ and $2^{36}\equiv 1 \bmod 37$ whence $2^{36}\equiv 1 \bmod 999$
So, for a start, we can reduce $499$ modulo $36$ before doing any of the detailed calculations.
Or notice that $2^{10}=1024\equiv 25 = 5^2\bmod 999$ and use Fermat-Euler with $5$ instead of $2$.
Or combine both approaches and notice some other things too.