# Calculate the remainder of $2^{118}/5$

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!

• 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

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

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

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

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.

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

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