Finding the remainder of a large number without the use of a calculator.

Question

How would I calculate the following without using a calculator: $152615278636986567767^{12345678}$ % $5$

I have gotten only the last digit by doing: $152615278636986567767$ % $10 = 7$

Therefore having $7^{12345678}$ % $5$.

I am unsure of how I should do the rest to find the final remainder.

I had a look at similar formats like How would I find the modulo of a large number without using a calculator that supports large numbers?, but I haven't learned any of the following rules/theorems.

Answer 1

I'm assuming you don't know Fermat's little theorem yet. So I won't tell you to use it.

But $7^1\% 5 = 2$.

And $7^2\% 2=2*7\% 5=14\% 4 = 4$

And $7^3\% 3 = 4*7\%5 = 28\% 5 = 3$

and $7^4\%4 = 3*7\%5 = 12\% 5 = 1$ and hey we're back to one!.

$7^5\%4 = 1*7\%5=7\% 5 = 2$. We're back where we started.

So we going to repeat and repeat in $4$ term cylce.

The eggponent is $12345678=12345676 + 2$ which goes through a bunch of four term cycles and two more. So $7^{12345678}\% 5 = 7^2 \% = 4$.

.....

Oh.... I guess I'm assuming it is intuitively obvious that if $a\% 5 = m$ and $b\% 5= n$ then $ab \% 5 = mn\% 5$......

I'll leave that to you to convince yourself it is clear.

Knowing this three things:

1. $(a+b)\% N = [(a\%N)+(b\% N)]\%N$
2. $(a\times b)\%N = [(a\%N)\times (b\%N)]\% N$
3. Theres only $5$ possible remainders (including $0$) so eventually these powers will repeat.

You should be able to solve this on your own.

Answer 2

As $152615278636986567767\equiv 7\mod 10$, we also have $152615278636986567767\equiv 7\equiv 2\mod 5$.

Now by lil' Fermat, as $2$ and $5$ are coprime, we have $2^4\equiv 1\mod 5$, so that $$152615278636986567767^{12345678}\equiv 2^{12345678}\equiv 2^{12345678\bmod4}=2^2\mod 5.$$