I'm interested in the following problem: do there exist infinitely many prime numbers $p$ such that $p^2|2^{n}+3$ for some natural number $n$?

Some motivation:

If we replace the function $2^n + 3$ with the $f(n)$ where $f \in \mathbb{Z}[x]$ is non-constant that this is true (follows Hensel lemma). So, it's rather natural to try proving this for some other non-polynomial functions. $2^n + 3$ is an easy example of such function. There is also another good reason: sequence $a_n = 2^{n} + 3$ satisfies the reccurence relation: $a_{n+2} = 3a_{n+1} - 2a_{n}$. And for example this problem is true for Fibonacci sequence. So, for Fibonacci it's easier even if the closed form of Fibonacci numbers is more complicated. But I think that the reason of this is that the Fibonacci numbers satisfy some "good" identities which other sequences don't have to share.

Now some remarks:

It's easy exercise to prove that there are infinitely many primes $p$ such that $p|2^{n}+3$. Also, if we try "correcting" $n$ to work also for $p^2$ and we try $m=n+k(p-1)$ we see that it is possible unless $p$ is Wieferich prime, i.e. satisfies $p^2|2^{p-1}-1$. And this gives us nothing as we don't know much about Wieferich primes...

This method can of course be generalized in such way: if $p|2^{n}+3$ and order of $2$ mod $p^2$ is greater than order of $2$ mod $p$ then we can find $m$ such that $p^2|2^{m}+3$. But I don't really think that it helps.

I'm interested in some information about this problem (especially if it's open or not) and also related problems. We can ask a general question: for which functions $f$ we know that this is true?

Edit: Sorry for the confusion with $k$, deleted.

  • 2
    $\begingroup$ In the first sentence, where does $k$ come in? $\endgroup$ Jan 30, 2010 at 2:42
  • 5
    $\begingroup$ I guess 2 is expected to be to be a primitive root mod p for infinitely many p, and if you're a primitive root mod p then you're highly likely to be a primitive root mod p^2, so I am guessing that the question "are there infinitely many primes p for which p^2 divides 2^n+3 for some n" is open but that the answer is conjectured to be "yes". $\endgroup$ Jan 30, 2010 at 7:35
  • $\begingroup$ I wanted to ask about $p^k|2^n+3$ but than I have changed my mind as I think $k=2$ is difficult enough ;) (and the general case could be easy if we would have solved $k=2$). I have corrected the post, thanks for pointing out. $\endgroup$
    – user3645
    Jan 30, 2010 at 9:38
  • $\begingroup$ Kevin: I also think that this is probably open. But about your argument: the condition $2^n$ gives all values mod $p^2$ is for sure much stronger than condition $2^n$ gives some certain value $a$ mod $p^2$. For example, there are infinitely many $p$'s for which $2^n \equiv \pm 1 \pmod{p^2}$ does have a solution. So, who knows, maybe it can be also proved for $a=-3$? Are there any odd $a$ besides $\pm 1$ for which we know that it holds? And of course the last question in the post remains: what about functions $f(n)$ for which we know that the problem holds? $\endgroup$
    – user3645
    Jan 30, 2010 at 10:14

2 Answers 2


(Edited as the comments below suggest)

The ABC conjecture seemed to me like it would play a roll, however it comes up a little short:

"Are there infinitely many primes $p$ so that for each $p$ there is some integer $n$ with $p^2|2^n + 3?"$

If the ABC conjecture is true, then this answer to this question is almost "no", but still there is a problem at the end of the argument.

The ABC conjecture states that for any $\epsilon > 0$ there is a constant $K_\epsilon$ so that for any co-prime triple $A < B < C$ with $A+B = C$ then $$C \le K_\epsilon\prod_{p|ABC}p^{1 + \epsilon}.$$

So, if there is such an infinite collection of primes, then for the corresponding infinite $n$ where this is true then $2^n + 3 = p^2C$ then $$p^2C \le K_\epsilon(6Cp)^{1+\epsilon}.$$

(Edited: The following sentence is incorrect "But this will clearly run into problems for sufficiently large $p.$" But I wanted to leave it so Kevin's comment makes sense.)

Note that as $C = C(p)$ is a function of $p$ then the $C^\epsilon$ (when $C$ is square-free, or nearly square-free) term may still allow this inequality to work.

  • 3
    $\begingroup$ "But this will clearly run into problems for sufficiently large p". But C=C(p) right? So if e.g. C(p) is a prime that's >> p then we have no contradiction, right? Or did I slip up? $\endgroup$ Jan 30, 2010 at 7:28
  • $\begingroup$ ah, that's true...the power of epsilon may just save the day if $C$ is square-free. I guess over function fields where there is no epsilon in the ABC theorem an analogous statement would be false. $\endgroup$
    – Ben Weiss
    Jan 30, 2010 at 7:33
  • 1
    $\begingroup$ Ben: I think it's highly likely that there are infinitely many such primes, because 2 is surely a primitive root mod p^2 for infinitely many primes and that's even stronger than what the OP is asking. $\endgroup$ Jan 30, 2010 at 7:38
  • 2
    $\begingroup$ For me you should leave it, but personally I think it's impossible that this problem is not true (because of Kevin's argument for example). $\endgroup$
    – user3645
    Jan 30, 2010 at 9:58
  • 1
    $\begingroup$ Ben: my honest advice is that you should leave it mostly as it is but (assuming you now believe that it doesn't quite work) point out where the problem is. Your post carries information! It says "ABC might be relevent: let's try it; here's what happens". Just edit it a bit to explain that you no longer think it solves the problem. I've seen this sort of behaviour lots of times. $\endgroup$ Jan 30, 2010 at 14:42

This is part of the question I asked on 5191. On my observation primes categorized themselves into 3 types, a)primes that doesn't divide the form of 2^x + c, b)primes that divides but a smaller had divided it already and c)primes that divides a new x usually larger primes. Once a prime divides a form in this case 2^x + 3 it will divide it infinitely periodically, so I believe even the form of p^k|2^x + c will be true. All primes that has a period of p-1 (totient = p-1) will always divide any forms. On the case of wiefirich prime is a special form, all integer divides a mersenne, so no problem with any p^k dividing a mersenne, but tying the order of mersenne 2^k - 1 to prime k, it could just be one of the small numbers properties that the 2 wiefirich primes what they are.


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.