0
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ Hint: $2^4\equiv1\pmod5$ $\endgroup$ – Simply Beautiful Art Aug 27 '17 at 19:13
  • $\begingroup$ @SimplyBeautifulArt I was going to suggest $2^2\equiv -1 \bmod 5$ $\endgroup$ – Mark Bennet Aug 27 '17 at 19:24
  • $\begingroup$ @MarkBennet Then see szw1710's answer. $\ddot\smile$ $\endgroup$ – Simply Beautiful Art Aug 27 '17 at 19:25
  • $\begingroup$ 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 $\endgroup$ – Raffaele Aug 27 '17 at 19:39
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How come you write 2^118 mod 4, and not mod 5? $\endgroup$ – IdiotNerd Aug 27 '17 at 19:26
  • $\begingroup$ @IdiotNerd Because $2^{\color{red}4}\equiv1\pmod5$ $\endgroup$ – Simply Beautiful Art Aug 27 '17 at 19:27
  • $\begingroup$ You misunderstood me: it's the exponent $118$ which is reduced mod. $4$ (because of Fermat), not $2^{118}$. $\endgroup$ – Bernard Aug 27 '17 at 19:28
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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