# $5^n+n$ is never prime?

In the comments to the question: If $(a^{n}+n ) \mid (b^{n}+n)$ for all $n$, then $a=b$, there was a claim that $5^n+n$ is never prime (for integer $n>0$).

It does not look obvious to prove, nor have I found a counterexample.

Is this really true?

Update: $5^{7954} + 7954$ has been found to be prime by a computer: http://www.mersenneforum.org/showpost.php?p=233370&postcount=46

Thanks to Douglas (and lavalamp)!

-
@Clearly when $n$ is a multiple of 5 then $5^{n} +n$ doesnt remain a prime. But we will have to think of other cases. – anonymous Sep 6 '10 at 7:11
It is also clear that n is even if the number is prime. Considering remainder on division by 6, 5^n will always be congruent to 1, so n must be congruent to 0 or 4 mod 6. – Jonas Meyer Sep 6 '10 at 7:19
@Asaf: Jonas means the number is prime => n is even, not the other direction – Soarer Sep 6 '10 at 8:31
WinPFGW: 5^(2*3977)+(2*3977) is 3-PRP! (1.9963s+0.0004s) – Douglas S. Stones Sep 6 '10 at 9:13
Note: I have checked that $5^n+n$ is composite for all $n \leq 1000$. – Pete L. Clark Sep 6 '10 at 9:21

A general rule-of-thumb for "is there a prime of the form f(n)?" questions is, unless there exists a set of small divisors D, called a covering set, that divide every number of the form f(n), then there will eventually be a prime. See, e.g. Sierpinski numbers.

Running WinPFGW (it should be available from the primeform yahoo group http://tech.groups.yahoo.com/group/primeform/), it found that $5^n+n$ is 3-probable prime when n=7954. Moreover, for every n less than 7954, we have $5^n+n$ is composite.

To actually certify that $5^{7954}+7954$ is a prime, you could use Primo (available from http://www.ellipsa.eu/public/misc/downloads.html). I've begun running it (so it's passed a few more pseudo-primality tests), but I doubt I will continue until it's completed -- it could take a long time (e.g. a few months).

EDIT: $5^{7954}+7954$ is officially prime. A proof certificate was given by lavalamp at mersenneforum.org.

-
I disagree with that heuristic. A better heuristic is that if there is no covering set, and $\sum 1/\log f(n)$ diverges, then there will be a prime. For example, it seems possible that there may be no primes of the form $2^{2^n}+1$ with $n \geq 5$. – David Speyer Sep 6 '10 at 12:20
In fact, if $\sum 1/log f(n)$ diverges and there's no covering set there should be infinitely many primes of form $f(n)$. – Michael Lugo Sep 6 '10 at 19:03
I posted a link at mersenneforum.org (mersenneforum.org/showthread.php?p=228745) -- I won't be able to complete the proof myself since I will be travelling. Also, their computers are probably significantly faster than mine. – Douglas S. Stones Sep 7 '10 at 1:04
Fermat's Little Theorem says if p is a prime then 3^p=3 (mod p). A 3-probable prime is a number q that satisfies 3^q=3 (mod q). q might not be prime (but probably is). [if instead q does not satisfy 3^q=3 (mod q) then it is guaranteed to not be a prime] – Douglas S. Stones Sep 8 '10 at 1:43
Two reasons (a) I don't know in advance which n to test, so it's most likely that I would end up testing many composite numbers for primality (so it's more efficient to run weaker tests first, trial division+Fermat's test) and (b) I already have WinPFGW installed and it tests for 3-PRP. – Douglas S. Stones Sep 8 '10 at 15:11

If $n$ is odd, then $5^n + n$ is always even because LSD of $5^n$ is always $5$ for $n \gt 0$. Hence, for odd $n ( n \gt 0)$, $5 ^n + n$ is composite.

-
As this is not an answer this post should be a comment. – yjj Sep 6 '10 at 9:05
@yjj: Crazy has only 1 reputation point. Remember what that was like? It means you can't comment. – TonyK Sep 6 '10 at 12:31
@TonyK Do not you think the rep needed for comment is too high? Examples like this are littered all over the site. I find it a bit strange that you are actually allowed to answer but not to comment. Perhaps, if you agree with me, you could bring it up on Meta. – Sawarnik Feb 15 '14 at 12:34

After reading Douglas S. Stones comment I asked mathematica to check if $5^{2\times 3977} + 2\times 3977$ is prime and after about $27$ seconds, found that it is indeed prime. So the claim $5^n +n$ is never prime is false.

Edit: It turns out the function I used in mathematica is not a deterministic algorithm. However we can still say the claim $5^n +n$ is never prime is false is most likely true.

-
To prove primality of numbers of this size can take months... – Douglas S. Stones Sep 6 '10 at 10:32
Is this primality test perfect or does it find "probable" primes? And does/can Mathematica give a certificate of primality? – ShreevatsaR Sep 6 '10 at 10:37
ShreevatsaR: Mathematica has a package NumberTheoryPrimeQ (I don't know the proper context in the newer versions) which uses either of Atkin-Morain or Pratt to provide a primality certificate. As Douglas said, however, it takes lots of time and memory to generate primality certificates for huge enough numbers. (If you have a gamer friend, you might want to borrow his/her PC for this ;)) – J. M. Sep 6 '10 at 11:20
On a somewhat off-topic note, we can see that this is (probably) a stereotype of mathematicians rather than gamers since P(fast computer|gamer) >> P(fast computer|mathematician) ;) – kahen Oct 14 '10 at 18:24