# $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, 2010 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. Sep 6, 2010 at 7:19
• @Asaf: Jonas means the number is prime => n is even, not the other direction
– user325
Sep 6, 2010 at 8:31
• WinPFGW: 5^(2*3977)+(2*3977) is 3-PRP! (1.9963s+0.0004s) Sep 6, 2010 at 9:13
• Note: I have checked that $5^n+n$ is composite for all $n \leq 1000$. Sep 6, 2010 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$. Sep 6, 2010 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)$. Sep 6, 2010 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. Sep 7, 2010 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] Sep 8, 2010 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. Sep 8, 2010 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.
– user899
Sep 6, 2010 at 9:05
• @yjj: Crazy has only 1 reputation point. Remember what that was like? It means you can't comment. Sep 6, 2010 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. Feb 15, 2014 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... Sep 6, 2010 at 10:32
• Is this primality test perfect or does it find "probable" primes? And does/can Mathematica give a certificate of primality? Sep 6, 2010 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 ;)) Sep 6, 2010 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) ;) Oct 14, 2010 at 18:24