<s>[INST] 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$)  
Thanks in advance!
 [/INST] 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.
</s>