# How to calculate last four digits of $2^{2017}$?

can u suggest me any short trick of solving these kind of problems. How to find last four digits of any number raised to some power ?

• – lab bhattacharjee Dec 14 '17 at 6:55
• The standard approach is to use modular arithmetic, with the Chinese remainder theorem and Euler's theorem. – Arthur Dec 14 '17 at 6:56
• Just to mention : TIFR GS 2018, conducted a few days ago, asked for the last three digits of this number. The answer was $072$, and the official (or rather, mine) solution says : note that $2^{n}$ and $2^{n+20}$ have the same last three digits after some time(for $n > 7$)! And therefore you find the last three digits of $2^{17}$. For four digits, you will have to proceed a little further. – Teresa Lisbon Dec 14 '17 at 7:02
• Have a look at math.stackexchange.com/a/2562678/44121 – Jack D'Aurizio Dec 14 '17 at 22:34

To compute this in terms of powers of $5$ and reduce modulo $5^4$ you can compute $$2^{2017}=2\cdot (1-5)^{1008}\equiv 2\cdot\left(1-5\binom{1008}1+25\binom {1008}2-125\binom {1008}3\right)\equiv$$and because of the factors $5^r$ you can reduce the binomials modulo $125, 25, 5$ respectively so $$\equiv2\cdot\left(1-5\cdot 8+25\cdot3-125\cdot 1\right)\equiv$$(which I did in my head using the indicated short cut) $$\equiv2\cdot-89\equiv 447$$

And $447$ leaves remainder $-1$ when divided by $16$ while $625$ leaves remainder $1$, so $447+625=1072$ will match residues modulo both $16$ and $125$.

Since $10^4 = 2^4 \times 5^4$, my first reaction is one should use Chinese remainder theorem.

For $2^4$, it is clear $2^{2017} \equiv 0 \pmod {2^4}$.

For $5^4$, we use following theorem

For $a,b \in \mathbb{Z}_{+}$ such that $\gcd(a,b) = 1$, we have $$a^{\varphi(b)} \equiv 1 \pmod b$$ where $\varphi(\cdot)$ is the Euler totient function.

For $a = 2$ and $b = 5^4$, we have $\varphi(5^4) = 4(5)^3 = 500$. This leads to $$2^{2017} = 2^{4(500)+17} \equiv 2^{17} \equiv 65536\times 2 \equiv 1072\pmod {5^4}$$

It turns out we are lucky. Since $1072 \equiv 0\pmod {2^4}$ already, we don't need CRT to conclude $2^{2017} \equiv 1072 \pmod {10^4}$. As a result, the last $4$ digits of $2^{2017}$ is $1072$.

• Another coincidence is that the answer uses same digits as the exponent 2017. +1 – Paramanand Singh Dec 14 '17 at 7:49

Hint: You want to find $2^{2017} \bmod 10000$. To do that, it suffices to find it $\bmod 16$ and $\bmod 625$. Finding it $\bmod 16$ is easy; to find it $\bmod 625$, use Euler's theorem that, if $\gcd(a,n)=1$, then

$$a^{\varphi(n)} \equiv 1\bmod n,$$

where $\varphi(n)$ is the Euler totient function. Can this reduce $2^{2017}$ into something more manageable?

• We need $\pmod{10^4}$ right? – lab bhattacharjee Dec 14 '17 at 6:56
• @labbhattacharjee Yes. I've fixed my answer. – Carl Schildkraut Dec 14 '17 at 7:02

I shall find $2^{2017-4}\pmod{10^4/2^4}$

As $2^2=5-1$

$\displaystyle2^{2012}=(5-1)^{1006}\equiv1-\binom{1006}15+\binom{1006}25^2-\binom{1006}35^3\pmod{5^4}$

Now $\displaystyle1006\equiv6\pmod{5^3}\implies\binom{1006}15\equiv5\cdot6\pmod{5^4}$

$\displaystyle\binom{1006}2\equiv15\pmod{5^2}\implies\binom{1006}25^2\equiv5^2\cdot15\pmod{5^4}$

and $\displaystyle\binom{1006}3\equiv0\pmod5\implies\binom{1006}35^3\equiv0\pmod{5^4}$

$\displaystyle\implies2^{2012+1}\equiv2(1-5\cdot6+5^2\cdot15)\equiv346\cdot2\pmod{5^4}$

Multiply out by $2^4$

• A little more efficient than my binomial method I think. – Mark Bennet Dec 14 '17 at 7:49

This is a particular case of computing $a^k$ modulo $n$. Here $n=10000$. The systematic method for doing this is "repeated squaring". As $2^{2017}=2(2^{1013})^2$, first work out $2^{1013}$ modulo $10000$, that is its last four digits. If these last four digits form the number $a$ then $2^{2017}\equiv 2a^2\pmod{10000}$, so find the last four digits of $2a^2$.

Of course to find the last four digits of $2^{1013}$ one proceeds recursively: $2^{1013}=2(2^{506})^2$, so find the last four digits of $2^{506}$ etc.

As others have noted, you want $$2^{2017}$$ mod $$10000$$.

Using the Carmichael function of $$10000=2^45^4$$, which is $$5^34=500$$,

we have $$2^{2017}\equiv{2^{17}}=131072\equiv1072\bmod10000$$.