# Prime divisors of numbers 2^n + 3

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.

-
In the first sentence, where does $k$ come in? – Theo Johnson-Freyd Jan 30 '10 at 2:42
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". – Kevin Buzzard Jan 30 '10 at 7:35
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. – user3645 Jan 30 '10 at 9:38
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? – user3645 Jan 30 '10 at 10:14

(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.

-
"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? – Kevin Buzzard Jan 30 '10 at 7:28
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. – Ben Weiss Jan 30 '10 at 7:33
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. – Kevin Buzzard Jan 30 '10 at 7:38
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). – user3645 Jan 30 '10 at 9:58
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. – Kevin Buzzard Jan 30 '10 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.

-