10
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 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$ Commented Jun 26, 2014 at 16:24
  • $\begingroup$ @GHfromMO Yes this is the question. $\endgroup$ Commented Jun 26, 2014 at 16:49

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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$ Commented Jun 26, 2014 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$ Commented Jun 26, 2014 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$ Commented Aug 9, 2014 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$ Commented Aug 10, 2014 at 6:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.