Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
4  
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
1  
BTW, see oeis.org/A064541. –  lhf Dec 9 '12 at 16:32
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. –  mixedmath Dec 14 '12 at 7:10
show 1 more comment

2 Answers 2

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

share|improve this answer
    
+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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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