63
$\begingroup$

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)!

$\endgroup$
9
  • $\begingroup$ @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. $\endgroup$
    – anonymous
    Commented Sep 6, 2010 at 7:11
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Sep 6, 2010 at 7:19
  • $\begingroup$ @Asaf: Jonas means the number is prime => n is even, not the other direction $\endgroup$
    – user325
    Commented Sep 6, 2010 at 8:31
  • 6
    $\begingroup$ WinPFGW: 5^(2*3977)+(2*3977) is 3-PRP! (1.9963s+0.0004s) $\endgroup$ Commented Sep 6, 2010 at 9:13
  • 1
    $\begingroup$ Note: I have checked that $5^n+n$ is composite for all $n \leq 1000$. $\endgroup$ Commented Sep 6, 2010 at 9:21

3 Answers 3

59
$\begingroup$

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.

$\endgroup$
13
  • 9
    $\begingroup$ 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$. $\endgroup$ Commented Sep 6, 2010 at 12:20
  • 2
    $\begingroup$ 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)$. $\endgroup$ Commented Sep 6, 2010 at 19:03
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Sep 7, 2010 at 1:04
  • 3
    $\begingroup$ 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] $\endgroup$ Commented Sep 8, 2010 at 1:43
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Sep 8, 2010 at 15:11
13
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ As this is not an answer this post should be a comment. $\endgroup$
    – user899
    Commented Sep 6, 2010 at 9:05
  • 50
    $\begingroup$ @yjj: Crazy has only 1 reputation point. Remember what that was like? It means you can't comment. $\endgroup$
    – TonyK
    Commented Sep 6, 2010 at 12:31
  • $\begingroup$ @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. $\endgroup$
    – Sawarnik
    Commented Feb 15, 2014 at 12:34
7
$\begingroup$

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.

$\endgroup$
4
  • 6
    $\begingroup$ To prove primality of numbers of this size can take months... $\endgroup$ Commented Sep 6, 2010 at 10:32
  • 1
    $\begingroup$ Is this primality test perfect or does it find "probable" primes? And does/can Mathematica give a certificate of primality? $\endgroup$ Commented Sep 6, 2010 at 10:37
  • $\begingroup$ 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 ;)) $\endgroup$ Commented Sep 6, 2010 at 11:20
  • $\begingroup$ 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) ;) $\endgroup$
    – kahen
    Commented Oct 14, 2010 at 18:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .