TIFR-2018-Maths-B: 9

Question

What are the last $3$ digits of $2^{2017}$?

• A. $072$
• B. $472$
• C. $512$
• D. $912.$

Answer 1

$\text{We need to compute $2^{2017}$ mod $1000$.}$

$\text{$2^{2017}$ mod $1000= 2^{2000}2^{17}$ mod 1000 =$(2^{2000}$ mod 1000 * $2^{17}$ mod 1000) mod 1000 }$

$\text{Since, $2^{17}$ mod 1000 = $(2^{10}$ mod 1000 * $2^7$ mod 1000) mod 1000 = 24*128 mod 1000 = 72}$

$\text{Now, to compute $2^{2000}$ mod 1000,  we can use the idea of chinese remainder theorem}$ $\text{because 1000 = 125*8 and 125 and 8 are co-prime and } $

$\text{$2^{2000}$ mod 125=1 because $\phi(125) = \phi(5^3) =125*(1-\frac{1}{5})= 125*\frac{4}{5}=100$ and }$

$\text{$2^{2000}$ mod 125= $(2^{100})^{20}$ mod 125 = $1^{20}$ mod 125 = 1}$

$\text{[Here, $\phi(.)$ is Euler’s Totient Function and $a^{\phi(n)}$ mod n = 1 when a and n are co-prime.}$

$\text{So, $2^{100}$ mod 125=1]}$

$\text{Now, $2^{2000}$ mod 8 =$2^3*2^{1997}$ mod 8 =$8*2^{1997} $ mod 8= 0 }$

$\text{Now, Take $x=2^{2000}.$ So, we have 2 linear congruences here:}$

$x \equiv 1 \mod 125$

$x \equiv 0 \mod 8$

$\text{First congruence gives $x= 125j + 1$ and put it in second congruence}$

$\text{$125j + 1 \equiv 0 \mod 8$, So, j=3,11,19,… i.e. j = 8k-5 for k=1,2,...}$

$\text{Now, put $j=8k-5$ in  $x= 125j + 1$ }$

$\text{We get, $x= 125(8k-5)+1 = 1000k-125*5 +1 = 1000k – 624$}$

$\text{So, $2^{2000}$ mod 1000 =x mod 1000 = (1000k – 624) mod 1000 = -624 mod 1000 = 1000-624 = 376}$

$\text{So, $2^{2017}$ mod 1000 = 376*72 mod 1000 = 072}$