# Does $2^n-n$ have infinitely often a prime divisor greater than $n$?

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?

• 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^n-n$ is really huge. E. g., for $n=42$ it is 2199023255531, and for $n=197$ it is 2678230073764983792569936820568604337537004989637988058833 – მამუკა ჯიბლაძე Nov 19 '16 at 7:30
• 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$. – Felipe Voloch Nov 19 '16 at 8:15
• @FelipeVoloch: ABC does help: The gcd of $2^{n}-n$ and $2^{n+1}-(n+1)$ is at most $n-1$. 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$. – Lucia Nov 19 '16 at 18:04

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

Let's try some elementary counting. On one hand, $\sum_{n=1}^N\log(2^n-n)\ge cN^2$. On the other hand, if we assume that no prime in the prime factorization of $2^n-n$, $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^n-n$. It remains to get some reasonable bounds for $Q(p,\ell)$.

The first key observation is that if $m<n$ are such that $k=n-m<p$ and $p$ divides both $2^m-m$ and $2^n-n$, then $p$ divides $(2^k-1)m-k$, 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^n-n$ (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^n-n$ and $2^m-m$ and notice that $k$ determines $m$ modulo $p^{\ell-\ell_p}$ where $p^{\ell_p-1}<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_2p-2\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.

• Taking the subsequence $n=2^N$ wont' this improve the bound for the largest prime factor of Mersenne number $2^k-1$, which is only $2k+1$? (k need not be prime). – joro Nov 24 '16 at 9:58
• @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. – 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=p-m-1$ 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.)

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