there are infinitely many numbers $n$ so that $2^n$ ends in $n$

Prove that there are infinitely many numbers $n$ so that $2^n$ ends in $n$.

I was thinking of using induction. I know that $2^{36}$ ends in $36$ and $2^{736}$ ends in $736$. Indeed, one can see that $2^{100}\equiv 1\pmod{125}$ by the Euler Fermat theorem so $2^{103}\equiv 8\pmod{1000}$. Hence $2^{736} = (2^{103})^{7}\cdot 2^{15} \equiv 8^7\cdot 2^{10}\cdot 2^5\equiv (2^{10})^2\cdot 2\cdot 24\cdot 32\equiv 24^3\cdot 64\equiv 824\cdot 64\equiv 736\pmod{1000}$. Thus the proof will be complete if I can show that if $2^{n}$ ends in $dn$, where $d$ is the digit before $n$, then $2^{dn}$ ends in $dn$, but I'm not sure how to show this inductive step. Perhaps the Euler-Fermat theorem or Fermat's Little theorem might be useful?

Edit: Yes, it seems like this question might be a duplicate but I think that this question needs more justification than the one linked in the first comment below. In particular, I don't see enough justification in the answers for that question as to why certain numbers of the form $n=100l+36$ satisfy $2^n$ ends in $n$.

Solution 1:

We prove the stronger result that there is such a number $w_{n}$ in the interval $[2^{n},10^{n}]$ for $n \geq 2$ such that $w_{n}$ is a multiple of $2^n$.

$\textbf{Background}:$ For $n \in \mathbb{N}$ and $p$ a prime we set $\text{ord}_{p}(n)$ to be the unique integer $a \geq 0$ so that $p^{a}|n$ and $p^{a+1} \not \div n$. I.e $\text{ord}_{2}(6) = 1$ and $\text{ord}_{2}(3) = 0.$

$\textbf{Claim}:$ For $n \geq 2$ there exists there exists $v_{n}\in \mathbb{N}$ which satisfies $2^{v_{n}}-v_{n} \equiv 0 \mod 10^{n}$ and $\text{ord}_{2}(v_{n}) \geq n$.

$\textbf{Proof}:$

Set $v_{2} = 36$ so that $\text{ord}_{2}(v_{2}) = 2 \geq 2$. Suppose we have $v_{2},...,v_{k}$ that satisifies the above condition, then

$$\text{ord}_{2}(2^{v_{k}})\geq k+1$$

$$1)\text{ }\text{ }2^{2^{v_{k}}}-2^{v_{k}} \equiv 2^{v_{k}}(2^{2^{v_{k}}-v_{k}}-1)\mod 10^{k+1}$$

Now $$2)\text{ }\text{ }2^{v_{k}} \equiv 0 \mod 2^{k+1}$$

$$3)\text{ }\text{ }\text{ }\begin{cases}2^{v_{k}}-v_{k} \equiv 0 \mod 5^k \\ 2^{v_{k}}-v_{k} \equiv 0 \mod 4\end{cases} \Rightarrow 2^{v_{k}}-v_{k} \equiv 0 \mod 4(5^k) \Rightarrow 2^{2^{v_{k}}-v_{k}}-1 \equiv 0 \mod 5^{k+1}$$

Thus by $1), 2)$ and $3)$

$$2^{2^{v_{k}}}-2^{v_{k}} \equiv 0 \mod 10^{k+1}.$$

Hence it suffices to take $v_{k+1}=2^{v_{k}}$.

$\textbf{Claim}$: For every $n \geq 2$ there exists an integer $d_{n} \in [0,10^{n}-1]$ which satisfies $\text{ord}_{2}(d_{n}) \geq n$ and $2^{d_{n}}-d_{n} \equiv 0 \mod 10^{n}$.

$\textbf{Proof}:$

Since we have $v_{n} = 2^{n}c_{n}$ for some integer $c_{n}$ we know that

$$2^{2^{n}c_{n}}-2^{n}c_{n} \equiv 0 \mod 10^{n}$$

$$2^{2^{n}c_{n}-n}-c_{n} \equiv 0 \mod 5^{n}$$

Note that for all $\gamma \in \mathbb{Z}$

$$2^{2^{n}(c_{n}+\gamma 5^{n})-n}-(c_{n}+\gamma 5^{n}) \equiv 0 \mod 5^{n}$$

There exists a unique $\gamma_{n} \in \mathbb{Z}$ so that $c_{n}+\gamma_{n}5^{n} \in (0,5^{n}-1]$ (it can't be $0$ for trivial reasons).

Now set $d_{n} = 2^{n}(c_{n}+\gamma_{n}5^{n})$.

The sequence $d_{2},d_{3},...$ contains infinitely many distinct non-negative integers such that $2^{d_{j}}$ ends in $d_{j}$ with $d_{j} \in [2^{j},10^{j}]$

Solution 2:

The link has shown that for k-digits n ($k\ge 2$), if $2^n \equiv n \pmod {10^k}$, the last two digits of n must be 36. And it is obvious that $n \ge 10^{k-1}\gt k$.

Given k-digits n (k\ge 2) that $2^n \equiv n \pmod {10^k}$, we have $2^n \equiv n \pmod {2^k}$ that's $2^k | n$ and $2^n \equiv n \pmod {5^k}$. We could assume $2^n -n =u\times 5^k$
Since $k\ge 2$, $4\times 5^{k-1} |10^k$, and and $\varphi(5^{k+1})=4\times 5^k$ and
so $2^{10^k} \equiv 1\pmod{5^{k+1}}$, for any integer a, we have $2^{n+a\times 10^k}\equiv 2^n \pmod{5^{k+1}}$, so $2^{n+a\times 10^k}-n-a\times 10^k \equiv 2^n-n-a\times 10^k = (u-a\times 2^k)5^k \pmod {5^{k+1}}$
so $2^{n+a\times 10^k}\equiv n+a\times 10^k \pmod {5^{k+1}}$ iff $a=u\times 2^{-k} \pmod 5$
Which means that given k digit n that $2^n \equiv n \pmod {10^k}$, we could find exact two k+1 digit n' so that $2^{n'} \equiv n' \pmod {5^{k+1}}$ and the last k digit of n' is n. For one of the n', the first digit is odd number and for another n', the first digit is even (the difference of the first digit of them is 5).

And since $2^k | n$,
if $2^{k+1} |n$, $2^{k+1} | n'$ iff the first digit of it is even
if n is not multiple of $2^{k+1}$, $2^{k+1}|n'$ iff the first digit of it is odd.

So we have proved that there're exact one k+1 digit n' so that $2^{n'}| \equiv n' \pmod {10^{k+1}}$ and the last k digit of n' is n.

For example, for k=2, we have $2^{36} \equiv 36 \pmod {10^2}$ since $2^{36} -36 \equiv (5-1)^{18}-36 \equiv {18\choose2}5^2-{18\choose1}5+1-36\equiv 3\times 5^2 \pmod {5^3} $, we should choose $a=3\times 2^{-2}\equiv 2\pmod 5$, so we should add 2 or 7 before 36
Since 36 is not multiple of $2^3=8$, we should add odd number, that's 7 before 36
so $2^{736} \equiv 736 \pmod {10^3}$
similarly, $2^{736} -736 \equiv -{368 \choose 3} 5^3 +{368 \choose 2} 5^2 -{368 \choose 1}5 +1 -736 \equiv 4\times 5^3 \pmod{5^4}$, $a=4\times 2^-3 =3 \pmod 5$, next n' should be 3736 or 8736.
Since 736 is multiple of $2^4$, n' with even first digit number should be used so next n' is 8736.