# 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$$.

• Yes, separately. You are doing it well.. Sep 29, 2013 at 20:09
• Do you know modular arithmetic and congruence relations modulo $n$? Sep 29, 2013 at 20:09
• That way is good. Perhaps more directly, use $4$; the remainder when $4^3$ is divided by $7$ is $1$, and $19$ is a multiple of $3$. Sep 29, 2013 at 20:13
• You might want to investigate Fermat's little theorem and generalisations like Euler's theorem en.wikipedia.org/wiki/Fermat's_little_theorem Sep 29, 2013 at 20:15
• I guess my question was more general. Could you use the remainders when divided by 10 to find the remainders when divided by 7? Sep 29, 2013 at 20:24

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^{n \mod p-1} \equiv a^{p-1} \equiv 1 \pmod p$$