# Existence of infinitely many integers $n$ such that $2^n$ ends with $n$

Prove that there exist infinitely many positive integers $n$ such that $2^n$ ends with $n$ in decimal notation, i.e. $2n = \ldots n$.

-
To clarify, you are trying to show there are infinitely many $n\in\mathbb{Z}$ so that $2^n-n\equiv0\pmod{10^{\lfloor\log_{10}(n)\rfloor+1}}$. Correct? –  robjohn Dec 9 '12 at 14:26
Yes, but isn't this more difficult to prove –  Farrukh12 Dec 9 '12 at 14:52
Since it is only a mathematical statement of your problem, it don't see how it could be more difficult. –  robjohn Dec 9 '12 at 14:54
BTW, see oeis.org/A064541. –  lhf Dec 9 '12 at 16:32
I changed your question back to the question to which the answerers provided and directed their answers. If you want to ask a different question, I encourage you to ask a different question but in a different post. –  mixedmath Dec 14 '12 at 7:10

Hint:

$$2^{36} = \dots 36$$ $$2^{736} = \dots 736$$ $$2^{8736} = \dots 8736$$ $$2^{48736} = \dots 48736$$ $$\dots$$ $$2^{5075353432948736} = \dots 5075353432948736$$ (I would add more, but there is an important football match going on at the moment)

Edit:

(I am not sure if this is a homework question, or a contest question, so just another hint)

You might try to prove that $2^{10^m}\equiv 1 \pmod{5^m}$ for $m\geq2$ (by induction).

-
+1 for the edit, as that hints at a solution. :-) –  robjohn Dec 9 '12 at 17:28
Actually, I needed to show $2^{10^m}\equiv1\pmod{5^{m+1}}$ for $m\ge2$. I used the totient function rather than induction. –  robjohn Dec 10 '12 at 9:05
Yes, you are right about needing $5^{m+1}$. It didn't occur to me to use the totient function, unfortunately. –  Old John Dec 10 '12 at 9:20

Since $\phi(5^{n+1})=4\cdot5^n$, for $n\ge2.$ $$2^{10^n}\equiv1\pmod{5^{n+1}}\tag{1}$$ Suppose for some $n\ge2$, $$2^k\equiv k\pmod{10^n}\quad\text{and}\quad k\equiv0\pmod{2^n}\tag{2}$$ then, for some $0\le a\lt5$, we have $$2^k\equiv a5^n+k\pmod{5^{n+1}}\tag{3}$$ Multiplying $(3)$ by a power of $(1)$ yields $$2^{d10^n+k}\equiv a5^n+k\pmod{5^{n+1}}\tag{4}$$ Using the Chinese Remainder Theorem, we can find $0\le d\lt10$ so that \begin{align} d&\equiv a3^n&\pmod{5}\tag{5}\\ d&\equiv k/2^n&\pmod{2}\tag{6} \end{align} $(5)$ implies that $a\equiv d2^n\pmod{5}$ which in turn implies $$a5^n\equiv d10^n\pmod{5^{n+1}}\tag{7}$$ $(4)$ and $(7)$ yield $$2^{d10^n+k}\equiv d10^n+k\pmod{5^{n+1}}\tag{8}$$ $(6)$ implies that $d5^n+k/2^n\equiv0\pmod{2}$ which in turn implies $$d10^n+k\equiv0\pmod{2^{n+1}}\tag{9}$$ $2^k\equiv k\pmod{10^n}\Rightarrow k\gt0$. Thus, $(9)$ implies $d10^n+k\ge2^{n+1}$ which implies $$2^{d10^n+k}\equiv0\pmod{2^{n+1}}\tag{10}$$ Therefore, $(9)$ and $(10)$ gives $$2^{d10^n+k}\equiv d10^n+k\pmod{2^{n+1}}\tag{11}$$ Thus, $(8)$, $(9)$, and $(11)$ yield the $n+1$ equivalent of $(2)$: $$2^{d10^n+k}\equiv d10^n+k\pmod{10^{n+1}}\quad\text{and}\quad d10^n+k\equiv0\pmod{2^{n+1}}\tag{12}$$ where $d$ is computed from $(3)$, $(5)$, and $(6)$.

Iterating $(3)$, $(5)$, $(6)$, and $(12)$, gives a sequence of $k$ that satisfy $(2)$.

Example

For $n=2$, only $k=36$ satisfies $(2)$.

$2^{36}\equiv3\cdot5^2+36\pmod{5^3}$, so $a=3$. Thus, we need to solve \begin{align} d&\equiv 3\cdot3^2\equiv2&\pmod{5}\\ d&\equiv 36/2^2\equiv1&\pmod{2} \end{align} so $d=7$, and the next term in the sequence is $k=736$ for $n=3$.

$2^{736}\equiv4\cdot5^3+736\pmod{5^4}$, so $a=4$. Thus, we need to solve \begin{align} d&\equiv 4\cdot3^3\equiv3&\pmod{5}\\ d&\equiv 736/2^3\equiv0&\pmod{2} \end{align} so $d=8$, and the next term in the sequence is $k=8736$ for $n=4$.

$2^{8736}\equiv4\cdot5^4+8736\pmod{5^5}$, so $a=4$. Thus, we need to solve \begin{align} d&\equiv 4\cdot3^4\equiv4&\pmod{5}\\ d&\equiv 8736/2^4\equiv0&\pmod{2} \end{align} so $d=4$, and the next term in the sequence is $k=48736$ for $n=5$.

$2^{48736}\equiv3\cdot5^5+48736\pmod{5^6}$, so $a=4$. Thus, we need to solve \begin{align} d&\equiv 3\cdot3^5\equiv4&\pmod{5}\\ d&\equiv 48736/2^5\equiv1&\pmod{2} \end{align} so $d=9$, and the next term in the sequence is $k=948736$ for $n=6$.

etc.

-