0

I have a problem:

$2^{118}/5$, calculate the remainder

I think I should use modular arithmetic but I cannot understand it.

I assume I should apply $a^t\equiv b^t\mod n $

I have so far written: $2^{118} \mod 5$

And I know that I should convert the exponent $118$ but I don't know in which way. Please advise!

Anton Grudkin
  • 2,955
IdiotNerd
  • 85
  • 4
    Hint: $2^4\equiv1\pmod5$ – Simply Beautiful Art Aug 27 '17 at 19:13
  • @SimplyBeautifulArt I was going to suggest $2^2\equiv -1 \bmod 5$ – Mark Bennet Aug 27 '17 at 19:24
  • @MarkBennet Then see szw1710's answer. $\ddot\smile$ – Simply Beautiful Art Aug 27 '17 at 19:25
  • The remainders of $2^k;;k=1,2,3,4,\ldots$ divided by $5$ are $2,4,3,1,2,4,3,1,2,4,\ldots\quad $ they are $4$ and they repeat themselves according with the remainder $r$ of $k/4$. I mean that $2^2,;2^6,;\ldots,;2^{114},;2^{118}$ will give the same remainder when divided by $5$. This gives the result which is $2^{118}/5$ gives remainder $4$. Caution: this works because $5$ is prime. If you try with $9$ it doesn't work – Raffaele Aug 27 '17 at 19:39

5 Answers5

3

Observe that (modulo $5$) $2^2\equiv -1$, so (taking $59$-th power) we get $2^{118}\equiv (-1)^{59}=-1\equiv 4$, so finally the remainder is $4$.

szw1710
  • 8,102
1

Use Lil' Fermat: as $2$ is not divisible by $5$, $\;2^4\equiv 1\pmod 5$, hence $$2^{118}\equiv2^{118\bmod 4}\equiv 2^2=4\pmod 5.$$

Bernard
  • 175,478
1

The not-quite-brute-force way to see it is to see that the remainders for powers $0,1,2,3,4$ go like $1,2,4,3,1$. So the pattern must repeat after that, meaning that multiplying by $2^4$ mod $5$ does nothing. Or in math notation

$$2^4 \equiv 1 \pmod 5.$$

Thus $2^x \equiv 2^y \pmod 5$ if $x \equiv y \pmod 4$. So it suffices to pick a small number $x$ such that $118 \equiv x \pmod 4$ and then directly calculate the remainder when $2^x$ is divided by $5$.

There are more elegant number-theoretic tricks that let you skip some of the calculation, but for a problem of this size you don't really need them.

Ian
  • 101,645
1

$\!\begin{align}{\bf Hint}\ \ {\rm mod}\ 5\!:\,\ \color{#c00}{2^{\large 4}\equiv 1}\,\Rightarrow\, 2^{\large 118} \equiv &\ \ 2^{\large \color{#0a0}2\ +\ \color{#c00}4\cdot 29}\\ \equiv &\ \ 2^{\large 2} (\color{#c00}{2^{\large 4}})^{\large 29}\\ \equiv &\ \ 2^{\large 2}(\,\color{#c00}1\,)^{\large 29}\\ \equiv &\ \ 2^{\large\color{#0a0} 2}\end{align}$

i.e. we can replace $\, 118\,$ by $\,\color{#0a0}2 = 118\bmod\color{#c00} 4\ $ because $\ 2^{\large \color{#c00}{4}}\equiv 1\pmod{5}$

i.e. exponents on $\,2\,$ can be considered $\!\bmod \color{#c00}4\,$ (when working $\!\bmod 5)$
because the powers of $\,2\,$ have a cyclic repeating pattern of length $\color{#c00}4$

Bill Dubuque
  • 272,048
0

Alternatively: $$2^{118}=2^{116}\cdot 2^2=(2^4)^{29} \cdot 4=16^{29}\cdot 4=...6\cdot 4=...4=...0+4.$$ Hence, the remainder is $4$.

farruhota
  • 31,482