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^nn$. (For example take $n=(p1)^{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?

1$\begingroup$ Some quick statistics  up to 200, the only $n$ without such $p$ are 1,2,4,5 and 16. On the other hand, for some $n$ in this range the smallest $p>n$ dividing $2^nn$ is really huge. E. g., for $n=42$ it is 2199023255531, and for $n=197$ it is 2678230073764983792569936820568604337537004989637988058833 $\endgroup$ – მამუკა ჯიბლაძე Nov 19 '16 at 7:30

6$\begingroup$ Curiously, the ABC conjecture implies immediately that a similar statement holds for $a^n  n$, for any $a>2$ but it doesn't for $a=2$. $\endgroup$ – Felipe Voloch Nov 19 '16 at 8:15

3$\begingroup$ @FelipeVoloch: ABC does help: The gcd of $2^{n}n$ and $2^{n+1}(n+1)$ is at most $n1$. From this and abc it is easy to check that one of them must have a prime factor larger than $n$ for all large $n$. $\endgroup$ – Lucia Nov 19 '16 at 18:04
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^NN}1)$.
The second factor is of the form $2^k1$ where $k=2^NN$ 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, p.1, Schinzel showed that the largest prime factor $p$ of $2^k1$ satisfies $p \ge 2k+1$ for $k > 12$.
So for $N$ large enough, we have infinitely often $2 \cdot (2^NN) +1 > 2^N=n$.
Let's try some elementary counting. On one hand, $\sum_{n=1}^N\log(2^nn)\ge cN^2$. On the other hand, if we assume that no prime in the prime factorization of $2^nn$, $n\le N$ is greater than $N$, then this sum can be rewritten as $\sum_{p\le N}\sum_{\ell\ge 1}Q(p,\ell)\log p$ where $Q(p,\ell)$ is the number of $n\in[1,N]$ such that $p^\ell$ divides $2^nn$. It remains to get some reasonable bounds for $Q(p,\ell)$.
The first key observation is that if $m<n$ are such that $k=nm<p$ and $p$ divides both $2^mm$ and $2^nn$, then $p$ divides $(2^k1)mk$, so $m$ is determined by $k$ modulo $p$. This implies that in every interval of integers of length $p$ there may be at most $C\sqrt p$ numbers $n$ such that $p$ divides $2^nn$ (otherwise there would be two different pairs with the same difference) and we get the first "nontrivial" bound $$ Q(p,\ell)\le C\frac{N}{\sqrt p} $$ This is quite good as long as small $\ell$ are concerned. Indeed, for the range of summation $\ell\le N^{1/3}$, say, we get only $$ N\cdot N^{1/3}\log N\sum_{p\le N}\frac 1{\sqrt p}=O(N^{11/6}\log N)\,. $$
Now we need to improve this bound for $\ell>N^{1/3}$. Note that in this case $p^\ell$ is huge compared to any fixed power of $N$. Thus we can try the same argument with arbitrary $m<n<N$ such that $p^\ell$ divides both $2^nn$ and $2^mm$ and notice that $k$ determines $m$ modulo $p^{\ell\ell_p}$ where $p^{\ell_p1}<N\le p^{\ell_p}$. But this number is still greater than $N$, so each difference is unique. This gives us the estimate $Q(p,\ell)\le C\sqrt N$, but this is not quite enough, so we now look at the differences.
If $p^\ell$ divides both $2^{k'}m'n'$ and $2^{k''}m''n''$ with $k''=k'+k$, then it also divides $2^km''n'm'n''$, so $k\ge \ell\log_2p2\log_2N\ge c\ell\log p$. This separation of the differences improves the bound to $$ Q(p,\ell)\le C\sqrt {\frac N{\ell\log p}}\,. $$ Taking into account that we need to sum in $\ell$ just up to $N/\log_2 p$, we finally get that large $\ell$ can contribute only $N\pi(N)=o(N^2)$.
Small morning edit To ensure that $2^km''n'm'n''\ne 0$ in the last part of the argument, just consider odd $n$ only in the whole story.

$\begingroup$ Taking the subsequence $n=2^N$ wont' this improve the bound for the largest prime factor of Mersenne number $2^k1$, which is only $2k+1$? (k need not be prime). $\endgroup$ – joro Nov 24 '16 at 9:58

1$\begingroup$ @joro It won't because a) the sequence $n=2^m$ is too sparse, so the product of first $N$ terms is just the square of the $N$th term and b) I cannot say anything at all about any individual $n$, it is all just about the "average" behavior. $\endgroup$ – fedja Nov 24 '16 at 14:00
Let $m>1$ be a natural number, and $p$ be a prime divisor of $(m+1)2^m+1$. Then $n=pm1$ does the trick.
EDIT: On second thought, there is a catch. As Ofir Gorodetsky suggested, it is not difficult to show that infinitely many primes may be obtained this way. But I do not know how to show that infinitely many of them will satisfy the inequality $p>m+1$. (Of course, actually there is a lot of them, but this may be tricky to prove.)

$\begingroup$ Nice. If we set $f(n)= (n+1)2^n +1$, then the observation that $f(n1)$ iscoprime to $n$ proves that your method indeed generates infinitely many primes. $\endgroup$ – Ofir Gorodetsky Nov 19 '16 at 15:43