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?

  • 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^n-n$ 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 $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$. $\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^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.

  • $\begingroup$ 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). $\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=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.)

  • $\begingroup$ 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. $\endgroup$ – Ofir Gorodetsky Nov 19 '16 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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