I think the question in the title is clear.  

Let $n\in \mathbb{N}$. It is a nice exercise to show that every prime number divides infinitely many terms of the sequence $2^n-n$. (For example take $n=(p-1)^{2m} , m\in \mathbb{N}$)  

I would like to show that there are infinitely many primes for which $2^n\equiv n\pmod{p}$ is actually satisfied for some $0<n<p$ which is equivalent to the question already existing in the title.  

Any ideas?



Does $2^n-n$ have infinitely often a prime divisor greater than $n$?
The answer is positive.


For natural $N$, let $n=2^N$. We are interested in large
prime factors of $2^{2^N}-2^N=2^N(2^{2^N-N}-1)$.


The second factor is of the form $2^k-1$ where $k=2^N-N$ is not
necessarily prime. These numbers are called Mersenne numbers
(different definition requires $k$ to be prime, we do not use it).


According to [this paper](https://math.dartmouth.edu/~carlp/PDF/murata4.pdf),
p.1, Schinzel showed that the largest prime factor $p$ of $2^k-1$
satisfies $p \ge 2k+1$ for $k > 12$.


So for $N$ large enough, we have infinitely often $2 \cdot (2^N-N) +1 > 2^N=n$.


