1
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ I think the proof of the proposition $$8^{4k}\equiv16\pmod{20}$$ should find a place in the post $\endgroup$ May 26 '19 at 11:35
  • $\begingroup$ 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. $\endgroup$
    – fleablood
    May 26 '19 at 22:32
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.