# Modular exponentitation (Finding the remainder)

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.

• The cyclic pattern is greatly simplified if you use mod distibutivity to factor $4$ from the mod - see my answer. May 26 '19 at 22:07

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.

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

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

• I think the proof of the proposition $$8^{4k}\equiv16\pmod{20}$$ should find a place in the post May 26 '19 at 11:35
• Perhaps. But the op had done calculations by manipulations correctly to get the powers of two results. I just wanted to point out his interpretation was too specific and all he need assume are multiples of 4. May 26 '19 at 22:32

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)\$$