# Primes dividing $2^a+2^b-1$

From Fermat's little theorem we know that every odd prime $p$ divides $2^a-1$ with $a=p-1$.

Is it possible to prove that there are infinitely many primes not dividing $2^a+2^b-1$?

(With $2^a,2^b$ being incoguent modulo $p$)

1. Obviously, If $2$ is not a quadratic residue modulo $p$ then we have the solution
$a=1, b=\frac{p-1}{2}$

2. If $2$ is a quadratic residue and the order of $2 \ modp$ is $r=\frac{p-1}{2}$
then the set $\{2^1,2^2,...,2^{\frac{p-1}{2}}\}$ is a complete quadratic residue system modp.
So,In this case, $p\mid2^a+2^b-1$ is equivalent to $p\mid x^2+y^2-1$ with $x^2,y^2$ being incogruent modp, which is always true for every $p\geq11$ .

3. It is not true that if $p \mid2^a+2^b-1$ and $q\mid2^{a'}+2^{b'}-1$ then $p\cdot q\mid 2^c+2^d-1$ .

There is the counterexample: $5\mid 2^1+2^2-1$ and $17\mid 2^1+2^4-1$ but
$5\cdot 17=85\not \mid2^a+2^b-1$.

We can see a few examples of numbers which have the questioned property :$3,7,31,73,89,...$
(In fact,every Mersenne prime does not divide $2^a+2^b-1$)

• Please confirm that I understand your question correctly: Are there infinitely many primes $p$ that do not divide any number of the form $2^a+2^b-1$ with $2^a\not\equiv 2^b\pmod{p}$? – GH from MO Jun 26 '14 at 16:24
• @GHfromMO Yes this is the question. – Konstantinos Gaitanas Jun 26 '14 at 16:49

This is a heuristic which suggests that the problem is probably quite hard. We have that $p | 2^{a} + 2^{b} - 1$ if and only if there is some integer $k$, $1 \leq k \leq p-1$ with $k \ne \frac{p+1}{2}$ for which $2^{a} \equiv k \pmod{p}$ and $2^{b} \equiv 1-k \pmod{p}$ are both solvable. If $r$ is the order of $2$ modulo $p$, then for each element $k$ in $\langle 2 \rangle$, the "probability" that $1-k$ is also in $\langle 2 \rangle$ is $\frac{r}{p-1}$ (assuming that $1-k$ is a "random element of $\mathbb{F}_{p}^{\times}$). So the probability that there are no solutions is about $\left(\frac{p-1-r}{p-1}\right)^{r} \approx e^{-\frac{r^{2}}{p-1}}$. (Note that if $r$ is even, then we have the trivial solution $2^{a} \equiv -1 \pmod{p}$, and $b = 1$.)
Thus, in order for there to be a solution, we must have that $r$ is small as a function of $p$, no bigger than about $\sqrt{p}$. This implies that $p$ must be a prime divisor of $2^{r} - 1$ of size $\gg r^{2}$. (For example, the prime $p < 5 \cdot 10^{5}$ that does not divide a number of the form $2^{a} + 2^{b} - 1$ for which $r$ is the largest is $p = 379399$ and for this number, $r = 1709$.)
However, it seems difficult to prove unconditionally that there are numbers of the form $2^{n} - 1$ with large prime divisors. Let $P(2^{n} - 1)$ denote the largest prime divisor of $2^{n} - 1$. Then, the strongest unconditional results (see the paper of Cam Stewart in Acta. Math. from 2013) take the form $P(2^{n} - 1) \geq f(n)$, where $f(n) = O(n^{1 + \epsilon})$ for all $n$. (Of course, we only need a result for infinitely many $n$, but allowing exceptions seems not to help.) Murty and Wong (2002) prove assuming ABC that $P(2^{n} - 1) \gg n^{2 - \epsilon}$ for all $n$, and Pomerance and Murata (2004) show that $P(2^{n} - 1) \gg \frac{n^{4/3}}{\log \log(n)}$ for all but a density zero subset of $n$, assuming GRH.
• Doesn't a random element in $\mathbb{F}_p^{\times}$ have order $r$ with probability $\frac{\varphi(r)}{p-1}$ instead of $\frac{r}{p-1}$? Probably your heuristic works still. – Joni Teräväinen Jun 26 '14 at 14:13
• Yes, but the chance a random element (and I'm treating $1-k$ as a random element) of $\mathbb{F}_{p}^{\times}$ is in a fixed subgroup of order $r$ is $\frac{r}{p-1}$. – Jeremy Rouse Jun 26 '14 at 14:49
• But it is known that the primes having $r < \sqrt{p}$ have zero density, and that conditionally on GRH, so do those with $r < p/\psi{(p)}$, for any function $\psi \to \infty$.. (By the way, it is completely elementary to see a certain positive density of primes with $r < \sqrt{p}$. The stronger result is contained in Pappalardi's paper "On the order of finitely generated subgroups..." in J. Number Theory 57, 1996. ) Hence we expect as in the linked problem that a density one set of primes will divide a value. – Vesselin Dimitrov Aug 9 '14 at 17:00
• [I meant of course that it is elementary to show the positive density of $p$ having $r > \sqrt{p}$, not "$<$;" and also that, given $\delta > 0$, there is an explicit $c(\delta) > 0$ for which the $p$ with $r < c\sqrt{p}$ are of density $< \delta$. The argument for this is the same as the one given in Charles Mathhews' article linked to here: mathoverflow.net/questions/60441/… ] – Vesselin Dimitrov Aug 10 '14 at 6:18