5
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ See math.stackexchange.com/questions/1844558/… $\endgroup$ – lab bhattacharjee Dec 14 '17 at 6:55
  • $\begingroup$ The standard approach is to use modular arithmetic, with the Chinese remainder theorem and Euler's theorem. $\endgroup$ – Arthur Dec 14 '17 at 6:56
  • $\begingroup$ 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. $\endgroup$ – Teresa Lisbon Dec 14 '17 at 7:02
  • $\begingroup$ Have a look at math.stackexchange.com/a/2562678/44121 $\endgroup$ – Jack D'Aurizio Dec 14 '17 at 22:34
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Another coincidence is that the answer uses same digits as the exponent 2017. +1 $\endgroup$ – Paramanand Singh Dec 14 '17 at 7:49
1
$\begingroup$

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?

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

Like How to find last two digits of $2^{2016}$,

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A little more efficient than my binomial method I think. $\endgroup$ – Mark Bennet Dec 14 '17 at 7:49
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.