Numbers of the form $m^2+2^n$

Question

I would like to show that there are infinitely many primes $p$ such that every number is congruent to $m^2+2^n$ modulo $p$ for some positive integers $m,n$.

This is what I have tried so far: if 2 is a primitive root modulo $p$, then clearly the claim is true since every number except 0 is of the form $2^n$ modulo $p$. Moreover, $0=(-1)+1$ and since $-1 \equiv 2^k$ for some $k$, we have $0 \equiv 1^2+2^k \pmod p$. However, we don't know if 2 is a primitive root modulo infinitely many primes.

I also tried to look at the set of quadratic residues modulo $p$. Let's denote this set by $Q_p$. Then we look at the sets $Q_p+2^k=\{q+2^k: q \in Q_p,~k\geq 0\}$ and define $S=\bigcup_k (Q_p+2^k)$. We need to show that $S=\mathbb{Z}_p$. I can show that the if $2$ is a quadratic residue modulo $p$ then the set $S$ is closed under multiplication by 2 modulo $p$ and has size greater than $3p/4$. Also the sum of the elements of $S$ is zero modulo $p$. I can't see a way forward.

Answer 1

$\newcommand\F{\mathbf{F}}$

Claim: For a positive density of primes $p$, the expression $m^2 + 2^n$ hits every residue class mod $p$.

Write $2 = \eta^{r}$ for some primitive element $\eta$ where $r | (p-1)$. One wants to know whether every element of $\F_p$ can be written as $y^2 + 2^n$. We now note that numbers of the form $y^2 + 2^n$ are exactly of the form

$$y^2 + 2^n = y^2 + x^r, \ x \ne 0,$$ because the powers of $\eta$ run over every element of $\F^{\times}_p$, and hence the powers of $2$ run over every perfect non-zero $r$th power. Thus the problem becomes showing that there are infinitely many $p$ so that the equation

$$y^2 = - x^r + z, \ x \ne 0$$

has a solution modulo $p$ for every $z$. (Note that $r$ depends on $p$, of course!) The case $z = 0$ is a little special, and never works when $p \equiv 7 \mod 8$ as noted in the comments. But there is a solution with $z = 0$ when $p \equiv 3 \mod 8$, since then $2$ is not a square, so $-2$ is a square.

Let's concentrate on the case $z \ne 0$. In this case, the curve

$$y^2 = -x^r + z$$

is the affine model of a smooth hyperelliptic curve of genus $g = r/2$ when $r$ is even and $g = (r+1)/2$ otherwise. The desingularization of the projective model of this curve has at most two points at infinity, and so, by the Weil conjectures, this curve always has a solution modulo $p$ as long as

$$p - 1 - 2 g \sqrt{p} > 0.$$

(Because the Weyl conjecture gives this as a lower bound for the number of points.) Hence we are in good shape as long as

$$\sqrt{p} > r + o(1)$$

Let $s$ be the multiplicative order of $2$. Then $rs = p - 1$, so equivalently we want $$s > \sqrt{p} + o(1)$$

So now the question becomes: are there infinitely many primes for which the multiplicative order $s$ of $2$ modulo $p$ is greater than $\sqrt{p}$?

Let us prove something more precise:

Claim: There are infinitely (positive lower density) many primes $p \equiv 3 \mod 8$ such that the multiplicative order of $2$ is at least

$$\sqrt{p} \cdot 1.698643 \ldots $$

which will do the job.

Proof: Let $p \equiv 3 \mod 8$ be prime. Then $2$ is not a quadratic residue. Thus $2$ has even order. On the other hand, $p - 1$ is not divisible by $4$. Hence the multiplicative order of $2$ is $s = 2k$ for some odd $k$. Note also that if $p$ has order $2k$ only when $p$ divides $2^k + 1$. So all we need to do is show there are more primes of the form $3 \mod 8$ than there are primes dividing $2^k + 1$ for relatively small $k$.

Let us give a lower bound for the number of primes $p < X$ for which $p \equiv 3 \mod 8$, but the order of $2$ modulo $p$ is at least

$$(1 + \epsilon) \sqrt{X} > (1 + \epsilon) \sqrt{p}.$$

Here $\epsilon > 0$ is small and fixed. Later in the argument we shall see that we win as long as $\epsilon < 0.698643 \ldots$.

The number of primes less than $X$ which are $3 \mod 8$ is

$$\frac{1}{4} \frac{X}{\log(X)}(1 + o(1)),$$

by the prime number theorem.

Now we have to take away those primes such that the order of $2$ is less than $(1 + \epsilon) \sqrt{X}$, and which are $3 \mod 8$. We only need a good enough upper bound on this set. By our analysis above, we only need to take away primes which divide $2^k + 1$ for some odd $k$ where $2k$ is less than $(1 + \epsilon) \sqrt{X}$. Let's just subtract the number of primes which divide $2^k +1$ for any odd $k$ with $2k < (1 + \epsilon) \sqrt{X}$. We will certainly count primes twice, and certainly count primes not of the form $3 \mod 8$, but that doesn't matter.

Let $\omega(n)$ denote the number of distinct prime divisors of $n$. A standard estimate gives, for all $\epsilon > 0$, that

$$\omega(n) \le \frac{\log(n)}{\log \log(n)} (1 + o(1))$$

for all sufficiently large $n$. It follows that the number of distinct prime divisors of $n = 2^{k} + 1 = 2^{2m+1} + 1$ (so now $4m < (1 + \epsilon) \sqrt{X}$) is at most

$$ \frac{2m \log(2)}{\log(m)}(1 + o(1))$$

for all sufficiently large $m$. Hence the number of primes we need to remove is of order bounded above by

$$\sum_{4m<\sqrt{X}(1 + \epsilon) } \frac{2m \log(2)}{\log(m)}(1 + o(1)) = \frac{\log(2)(1+ \epsilon)^2}{8} \frac{X}{\log(X)}(1 + o(1)).$$

So we are in good shape as long as

$$\frac{\log(2)(1 + \epsilon)^2}{8} < \frac{1}{4},$$

or

$$(1 + \epsilon) < \sqrt{\frac{2}{\log(2)}} =1.698643\ldots$$

Answer 2

Here's an answer, under the assumption that there are infinitely many Sophie Germain primes equivalent to $1\bmod 4$.

Assume $p$ such an odd prime, and let $q=2p+1$. Then, as

$$2^{2p}\equiv 1\bmod q,$$

we see that, letting $d=\mathrm{ord}_q(2)$, $d\in\{1,2,p,2p\}$. As $q>3$, $q\nmid 2^2-1$, so $d\in\{p,2p\}$. If $d=2p$, then $2$ is a primitive root $\bmod q$, and thus $2^n$ takes on all nonzero values $\bmod q$. As such, we can represent all nonzero values $\bmod q$ by taking $m=0$, and can represent $0$ by taking $m=1$ and $n$ so $2^n\equiv -1\bmod q$.

If $d=p$, this would make $2$ a quadratic residue $\bmod q$. But $p\equiv 1\bmod 4\implies q\equiv 3\bmod 8$. However, it is known that $2$ is never a quadratic residue $\bmod$ any prime that is $\equiv 3\bmod 8$ (see here, for example), so this case cannot hold.

Using this idea and the technique of 2012 IMO Shortlist N8 I think this sort of thing can probably be extended to show the claim if there are infinitely many primes $p$ so that $2kp+1$ is prime and some suitable congruences hold, given any fixed odd $k$. I'm not sure about the details though (I think the solution to that particular problem should be able to be modified to provide the result for $k=5$).