Calculate $2^{5104} \bmod 10$ using mental arithmetic

Question

I am practising interview for Jane Street's trader internship and I found the following question.

Question: Calculate $2^{5104} \bmod 10$ using mental arithmetic.

I know that $2^5 \bmod 10 \equiv 2 \bmod 10.$ So, \begin{align*} 2^{5104} & = (2^5)^{1020} 2^4 \\ & \equiv 2^{1020}2^4 \\ & = (2^5)^{204}2^4 \\ & \equiv(2^5)^{40}2^8 \\ & \equiv (2^5)^8 2^8 \\ & \equiv (2^5)^3 2 \\ & \equiv 6 \bmod 10. \end{align*}

However, I find the calculations above very taxing if I use mental arithmetic. I believe there should be a faster way to answer the question but I am not able to find one.

Answer 1

if a number is not divisible by five, its fourth power is equivalent to $1 \pmod 5$

Answer 2

The cycle of units digits goes $2,\ 4,\ 8,\ 6,\ 2,...$, in a cycle of length 4 after the initial term of 1. $5104\equiv 4\pmod 4$, so the answer is the fourth term in the cycle which is $6$.

Answer 3

$$2^{5104}\equiv 16^{1276}\pmod{10}$$ $$\equiv 6\pmod {10}$$

Answer 4

This is the same as determining the units digit of $2^{5104}$. The units digit of the powers of $2$ repeat in the sequence $2,4,8,6$ (i.e. the $(4k+i)$th power of $2$, where $k\in\mathbb{Z}$ and $1\leq i\leq 4$, is the $i$th term in the sequence). Since $5104$ is a multiple of $4$, the answer is $6$.

Answer 5

What is the remainder when you divide the exponent by 4?

If it is $0$ then last digit will be $6$. When it is $1$ then last digit will be $2$. For $2$ as remainder, last digit will be $4$ and finally for $3$, last digit is going to be $8$.But all this does not work when the exponent is $0$. For that case, last digit is $1$. So in present case, as the exponent $5104$ is wholly divisible by $4$, the last digit will be $6$.

The divisibility of a number by $4$ is not difficult to check either. You just need to check number formed by the last two digits of the given number. The remainder that we get by dividing this number by 4 will be same as the remainder we get in case of original number. For the present case the two digit number is $04$ which is wholly divisible by $4$. And hence the original number $5104$ is also wholly divisible by $4$.

Answer 6

The Chinese Remainder Theorem says: $$2^{5104}\equiv x \pmod{2\cdot 5} \iff \begin{cases}2^{5104}\equiv x\pmod 2 \\ 2^{5104}\equiv x\pmod 5\end{cases}$$ It follows that $x\equiv 0\pmod 2$ and $x\equiv 1\pmod 5$.

Consequently $x\equiv 6\pmod{10}$.

Answer 7

$$2^{4n+2}=(5-1)^{2n+1}=-(1-5)^{2n+1}$$

$$\equiv-1\pmod5\equiv4$$

$$\implies2^{4n+4}\equiv4\cdot2^2\pmod{5\cdot2^2}$$

Answer 8

Mental arithmetic comes with practice. For $n>0$: $$2^{n}\equiv 2,4,8,6 \pmod{10} \Rightarrow 2^{5104}\equiv 2^{4\cdot 1276}\equiv 6\pmod{10}\\ 3^{n}\equiv 3,9,7,1 \pmod{10} \Rightarrow 3^{5104}\equiv 3^{4\cdot 1276}\equiv 1\pmod{10}\\ 4^{n}\equiv 4,6 \pmod{10} \Rightarrow 4^{5104}\equiv 4^{2\cdot 2502}\equiv 6\pmod{10}\ \ \ \ \ \ \ \ \\ 7^{n}\equiv 7,9,3,1 \pmod{10} \Rightarrow 7^{5104}\equiv 7^{4\cdot 1276}\equiv 1\pmod{10}\\ 8^{n}\equiv 8,4,2,6 \pmod{10} \Rightarrow 8^{5104}\equiv 8^{4\cdot 1276}\equiv 6\pmod{10}\\ 9^{n}\equiv 9,1 \pmod{10} \Rightarrow 9^{5104}\equiv 9^{2\cdot 2502}\equiv 1\pmod{10} \ \ \ \ \ \ \ \ $$ Different examples: $$2^{n}\equiv 2,4,8,6 \pmod{10} \Rightarrow 2^{5102}\equiv 2^{4\cdot 1275+2}\equiv 4\pmod{10}\\ 9^{n}\equiv 9,1 \pmod{10} \Rightarrow 9^{5105}\equiv 9^{2\cdot 2502+1}\equiv 9\pmod{10}$$ Can you find: $2^{325} \bmod 10$? $13^{1234} \bmod 10$? Answer:

$2^{n}\equiv 2,4,8,6 \pmod{10} \Rightarrow 2^{325}\equiv 2^{4\cdot 81+1}\equiv 2\pmod{10}\\13^n\equiv 3^{n}\equiv 3,9,7,1 \pmod{10} \Rightarrow 13^{1234}\equiv 3^{4\cdot 308+2}\equiv 9\pmod{10}$

Answer 9

Notice $\,\ 2^{\large 4+4N}\!\bmod 10 \, =\, \color{#c00}2\overbrace{(2^{\large 3} \color{#0a0}2^{\large\color{#0a0}4N}\bmod 5)}^{\textstyle \color{#0a0}{2^{\large 4}}\!\equiv 1\pmod{\!5}} = 2(3)$

by applying $\ \color{#c00}ab\bmod \color{#c00}ac\, =\, \color{#c00}a(b\bmod c) = $ $\!\bmod\!$ Distributive Law to factor out $\,\color{#c00}{a=2}$