Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
@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
2  
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
5  
WinPFGW: 5^(2*3977)+(2*3977) is 3-PRP! (1.9963s+0.0004s) –  Douglas S. Stones Sep 6 '10 at 9:13
1  
Note: I have checked that $5^n+n$ is composite for all $n \leq 1000$. –  Pete L. Clark Sep 6 '10 at 9:21
show 4 more comments

3 Answers

up vote 49 down vote accepted

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.

share|improve this answer
7  
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
2  
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
3  
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
3  
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
2  
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
show 7 more comments

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.

share|improve this answer
    
As this is not an answer this post should be a comment. –  yjj Sep 6 '10 at 9:05
43  
@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 at 12:34
add comment

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.

share|improve this answer
6  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.