9
$\begingroup$

Can anyone please help me on the following proof:

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

  • 1
    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.2012-12-14

2 Answers 2

9

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

  • 0
    Yes, you are right about needing $5^{m+1}$. It didn't occur to me to use the totient function, unfortunately.2012-12-10
4

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.