Finding $a^n \bmod b$?

Question

What is a good algorithm for finding the remainder?

For example: What would be the algorithm for finding the solution of $103^{45} \bmod 5$?

Answer 1

First, simplify the base. $103\equiv 3\mod 5$. Then $3^2\equiv -1\mod 5$, so that $3^{44}\equiv 1\mod 5$, and $103^{45}\equiv 3^{45}\equiv 3\mod 5$.

As a general rule, you will want to reduce the base so it is smallest in absolute value. Note I chose $-1$ instead of $4$ to carry out the computation. Also, you will want to choose an appropriate way to split the exponent if this has a direct impact in your process: $45=2\cdot 22+1$ is useful, since $3^2=-1$.

In the general case, you can work with exponents after reducing the base. In this case the exponent of $103\equiv 3$ modulo $5$ is simply $\varphi(5)=4$, but generally the exponent might be smaller, thus helping the computation. This is relevant to your question.

Answer 2

Use Fermat's little theorem.

$a^{p-1}$ modulo $p$ is $1$ if $p$ is a prime and $a$ and $p$ are relative primes

In this case $103^4$ modulo $5$ is $1$.

So $103^{44}$ modulo $5$ is also $1$.

And $103^{45}$ modulo $5$ is $103$

So $103$ modulo $5$ is $3$.

So as final answer $103^{45}$ modulo $5$ is $3$.

I don't know how to write an algorithm but hope it helps.

Answer 3

First note that $103$ and $5$ are coprime numbers so from Euler Theorem we have:

If $a$ and $p$ are coprime this follows:

$$a^n \equiv a^{n \mathop\bmod \phi(p)} \pmod p$$

So we have:

$$103^{45} \equiv 103^{45 \mathop\bmod 4} \equiv 103 \equiv 3 \pmod p$$

If $a$ and $p$ are not coprime numbers then you can prime factorize him and apply this algorithm. If in the prime factorization one prime number shows more than once, then you can try to use the Hensel's lemma for lifting.

And then use Chinese Remainder Theorem to "glue" the answers together.

Answer 4

First of all check whether $b$ is a prime. If is it so then you already know that $a^b\equiv a(mod~b)$ (see Fermat's Theorem). Use that. Otherwise find the remainder that $a$ leaves when divided by $b$, let it be $r$, then find $r^n~mod~b$