What are the last 3 digit of 2^2017?

I will provide two methods for this.

Method 1 (Easy way) :

USE A CALCULATOR. You will get the answer in a matter of seconds like I got.

Clearly, the answer is 072.

Method 2 (Slight harder way) :

Here, I want to find the answer without using the calculator. Let's try it.

Note:- I will be making use of Congruence Modulo and Euler's Theorem, so these are the prerequisites.

Another way to put the question is “Find the remainder when 22017$2^{2017}$ is divided by 1000”.

First of all we factorise 1000 as:

1000=23×53$1000=2^3\times 5^3$

Next, we find the remainder by 23$2^3$ and 53$5^3$seperately.

It's obvious that 23$2^3$ divides 22017$2^{2017}$. Hence,

22017≡0(mod8)$2^{2017}\equiv 0(mod8)$

Now to find the remainder by 125 (or 5^3), we use Euler's Theorem. Euler's theorem is applicable in this case since gcd(2,125)=1$gcd(2,125)=1$.

Φ(125)=125(1−15)=100$\mathrm{\Phi }(125)=125(1-\frac{1}{5})=100$

Hence, 2Φ(125)≡1(mod125)$2^{\mathrm{\Phi }(125)}\equiv 1(mod125)$

⟹2100≡1(mod125)$⟹2^{100}\equiv 1(mod125)$

⟹22000≡1(mod125)$⟹2^{2000}\equiv 1(mod125)$

⟹22017≡217(mod125)$⟹2^{2017}\equiv 2^{17}(mod125)$

Since 217=131072,217≡72(mod125)$2^{17}=131072,2^{17}\equiv 72(mod125)$

⟹22017≡72(mod125)$⟹2^{2017}\equiv 72(mod125)$

At this point, one may apply Chinese Remainder Theorem but checking few cases will yield the answer faster.

Since the number leaves a remainder 72 when divided by 125, the last digits can be:

125×0+72=072$125\times 0+72=072$, or

125×1+72=197$125\times 1+72=197$, or

125×2+72=322$125\times 2+72=322$, or

125×3+72=447$125\times 3+72=447$, or

125×4+72=572$125\times 4+72=572$, or

125×5+72=697$125\times 5+72=697$, or

125×6+72=822$125\times 6+72=822$, or

125×7+72=947$125\times 7+72=947$

We also know that the number is divisible by 8. The only number from the above list which is divisible by 8 is 72. Hence the answer is 072.

---

I would like to share one more thing. I calculated 2^17 in my head (since use of calculator is not allowed). How did I do that? Let's see:

210=1024$2^{10}=1024$

⟹220=10242=(1000+24)2$⟹2^{20}={1024}^2=(1000+24{)}^2$

=10002+2×1000×24+242$={1000}^2+2\times 1000\times 24+{24}^2$

=1000000+48000+576$=1000000+48000+576$

=1048576$=1048576$

Now divide this number by 8 to get 2^17.

10485768=131072$\frac{1048576}{8}=131072$

Easy, no?