Finding Remainder Using Base $10$ or $5$ I am trying to find the remainder of $4^{220}$ when divided by $7$.

$$4^{220}=2^{440}$$

Now had the question been what is the remainder of $2^{220}$ when divided by $10$, you would simply look at cycles in the last digit.

Last.Digit($2^1$)=$2$
Last.Digit($2^2$)=$4$
Last.Digit($2^3$)=$8$
Last.Digit($2^4$)=$6$
...

So the repeating cycle is $2$,$4$,$6$,$8$. Even if the question had asked the remainder if divided by $5$, one could use the last digits of $2^n$ to find the solution. Is there a way to find the remainder using this cycle when divided by $7$? Or do I literally have to compute the remainder of each power divided by $7$, as such

Remainder of ($2^1$,$7$)=$2$
Remainder of ($2^2$,$7$)=$4$
Remainder of ($2^3$,$7$)=$1$
...

A repeating cycle of $3k$. So $440=3(146)+2$, Hence the remainder is $4$.
 A: In general, if $n$ is prime and $a$ is not divisible by $n$, then $a^{n-1} = 1$ is the remainder when you divide by $n$. Hence if you already know remainders of $a^1,a^2,\ldots,a^{n-2}$ when you divide by $n$, then you can get the remainder for $a^M$ for any $M \geq n$ by exploiting the cycle like you did. In your case, you have $2^3 = 1$ is the remainder when you divide by $7$, which is even better than knowing $2^6 = 1$ is the remainder when you divide by $7$, so you only need to know the remainders of $2$ and $4$ when you divide by $7$ in order to establish the cycle and do your computation. In general this can always happen; you may very well have $a^k = 1$ as the remainder when you divide by $n$, where $k$ is a smaller divisor of $n-1$. Or it may require the full $k=n-1$ to get remainder of $1$ when you divide by $n$, in order to get the cycle. But the point is you'll always get a cycle of some length $\leq n$, so you can do your computations like you did. In general, knowing the cycle for some $n$ will not help you figure out the cycle for a different coprime choice of $n$, to answer the other part of your question you alluded to.
A: All you need is just a little modular arithmetics. Not that the modulo is a prime number and the base and the modulo ar coprime numbers, so the Fermat's Little Theorem is your friend here. We know then that the follwing statement holds:
$$a^{n \mod p-1} \equiv a^{p-1} \equiv 1 \pmod p$$
Now just plug the values and you'll be able to obtain a solution quite easily.
