Modular exponentitation (Finding the remainder)

Question

I want to find the remainder of $8^{119}$ divided by $20$ and as for as i do is follows:

$8^2=64\equiv 4 \pmod {20} \\ 8^4\equiv 16 \pmod {20} \\ 8^8\equiv 16 \pmod {20}\\ 8^{16}\equiv 16 \pmod {20}$

from this i see the pattern as follows $8^{4\cdot 2^{n-1}} \text{is always} \equiv 16 \pmod {20} \,\forall n \ge 1$

So, $\begin{aligned} 8^{64}.8^{32}.8^{16}.8^7 &\equiv 16.8^7 \pmod{20}\\ &\equiv 16.8^4.8^3 \pmod{20} \\ &\equiv 16.8^3 \pmod {20}\end{aligned}$

And i'm stuck. Actually i've checked in to calculator and i got the answer that the remainder is $12$. But i'm not satisfied cz i have to calculate $16.8^3$ Is there any other way to solve this without calculator. I mean consider my condisition if i'm not allowed to use calculator.

Thanks and i will appreciate the answer.

Answer 1

You are almost there. You can reduce anything modulo $20$ so:

$$16\times 8^3\equiv 16\times 8^2\times 8\equiv 16\times 4 \times 8\equiv64\times 8\equiv 4\times 8\equiv 12$$

You could also have used $16\equiv -4$ if it had helped - sometimes negative numbers make life easier, but it was not necessary here.

Answer 2

$8^n=(2^3)^n=2^{3n}$

As $(2^{3n},20)=4$ for $n\ge1$

Let's find $2^{3n-2}\pmod5$

Now $2^{3n-2}\equiv2^{(3n-2)\pmod4}\pmod5$ as $\phi(5)=4$

$\implies2^{3n}\equiv4\cdot2^{(3n-2)\pmod4}\pmod{20}$

Here $n=119\implies3n-2=3\pmod4$

Answer 3

Although $8^{4\cdot 2^{n-1}}\equiv 16\pmod {20} $ for all positive integer $n $, it is actually much simpler:

$8^{4k}\equiv 16\pmod {20} $ for all $k>0$. That is for any multiple of $4$, not just $4$times powers of $2$.

And furthermore $8^{4k+1}\equiv 16*8\equiv -4*8\equiv-32\equiv 8\pmod {20} $ for $k>0$

And $8^{4k+2}\equiv 8*8\equiv 4\pmod {20} $

And $8^{4k+3}\equiv 4*8\equiv 32\equiv 12\pmod {20} $.

Answer 4

Using $\, ab\bmod ac\, =\, a\,(b\bmod c) $ = mod Distributive Law to factor out $\,a =4\,$ yields

$\ \ \ \ 8^{\large 3+4K}\!\bmod 20\, =\, 4\,(\underbrace{2\cdot \color{#0a0}{8^{\large 2}}\,\color{#c00}8^{\large \color{#c00}{4}K}}_{\Large 2\, (\color{#0a0}{-1})\,\color{#c00}1^{\Large K}}\bmod 5) = 4(3)\ $