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!

  • 4
    $\begingroup$ 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}$? $\endgroup$ – GH from MO Jun 26 '14 at 16:24
  • $\begingroup$ @GHfromMO Yes this is the question. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Joni Teräväinen Jun 26 '14 at 14:13
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Jeremy Rouse Jun 26 '14 at 14:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Vesselin Dimitrov Aug 9 '14 at 17:00
  • 1
    $\begingroup$ [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/… ] $\endgroup$ – Vesselin Dimitrov Aug 10 '14 at 6:18

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.