Tell me more ×
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.
up vote -4 down vote favorite

Is $n^2+n+41$ prime for all whole numbers $n$?

Furthermore, how can we prove/disprove this?

Oh, sorry, I meant 41...

share|improve this question
1  
you'd better think before – Savinov Evgeny Jan 23 '12 at 23:33
2  
@Kannappan: There is a prime generating function (although it's not useful) that returns primes for all positive integers. In particular, I think of Mill's formula. But there is no prime generating polynomial. – mixedmath♦ Jan 23 '12 at 23:38
1  
@David Faux: Numerical experimentation is a good thing. Pick $n=1$. Not prime. End of story. If for some reason you didn't try $1$, let $n=3$. We get $65$, finished. Or try $n=6$. We get $95$. We also get a non-prime at $n=8$. And at $n=9$. We seem to get mostly non-primes! – André Nicolas Jan 23 '12 at 23:39
1  
@David Faux: With $41$ it is a well-known example due to Euler. Indeed $40$ is the smallest positive $n$ that gives a non-prime, and $41$ is next. For not too large $n$, this polynomial is often prime. But it is not known whether there are infinitely many $n$ such that $n^2+n+41$ is prime! – André Nicolas Jan 24 '12 at 0:25
2  
@David Faux: Let $P(n)$ have positive lead coefficient. For $n$ large enough, $P(n)$ is increasing. Pick such a large $n$, say $a$, such that $P(a)>1$. Let $p$ be a prime divisor of $P(a)$. Then $P(a+p) \equiv P(a)=0 \pmod{p}$. But $P(a+p)>p$, so $P(a+p)$ is not prime. – André Nicolas Jan 24 '12 at 1:06
show 3 more comments

5 Answers

up vote 0 down vote accepted

Since the question has been modified but the answer is still "no", let me answer the question raised in the comments. (What follows is all standard, I am just writing it to try and put the question to bed.)

Let $p$ be a polynomial, not identically zero, with non-negative integer coefficients. If $p(0)=0$ then $n$ divides $p(n)$ and $p(n)/n > 0$ for every positive integer $n$. If $p(0)=c$ for some nonzero integer $c$, then $c$ divides $p(2c)$, and unless $p$ is constant we will get $p(2c)/c > 0$.

EDIT as Gerry Myerson points out, the original argument I gave is insufficient when $c=1$. I think the following patch should work.

Let $p$ be a polynomial, not identically zero, with non-negative integer coefficients. If $p(0)=0$ then $p(4)$ is strictly positive and divisible by $4$, hence composite. Otherwise, we note that since $p(0)\geq 1$, $p(1)$ is strictly greater than $1$. Set $m=p(1)$ and note that $p(1+m)-p(1)$ is strictly positive and divisible by $m$ (because any positive power of $1+m$ is congruent to $1$ modulo $m$), so that $p(1+m)=km$ for some integer $k\geq 2$.

If one considers polynomials $p$ with arbitrary integer coefficients: my suspicion is that one can still always find a positive integer $n$ such that $p(n)$ is composite and non-zero, but I have not thought through the details properly.

** FURTHER EDIT** Thanks to Gerry Myerson again, this time for pointing out that in between my initial wrong proposal and my edited version, André sketched a better version of this approach in comments to the original question. I would encourage people to vote up his comment instead of this answer.

share|improve this answer
1  
What if $c=\pm1$? – Gerry Myerson Jan 24 '12 at 1:29
@GerryMyerson: good point, I was sloppy. I have attempted to supply a replacement argument which should suffice – user16299 Jan 24 '12 at 3:23
1  
Looks good. I think you'll find Andre's argument in one of his comments gets around the difficulties nicely. – Gerry Myerson Jan 24 '12 at 3:44
up vote 3 down vote

No. For $n=1$, we have that $$1^2+1+53=55=5\times 11.$$

share|improve this answer
May be $1^2$ would be meaningful! – user21436 Jan 23 '12 at 23:48
Now my +1, though you didn't tell me you edited it! – user21436 Jan 24 '12 at 0:11
up vote 3 down vote

$n=53$. ${}{}{}{}{}{}{}{}{}{}$

share|improve this answer
+1 "effortless" answer! You are the only one who never had to evaluate with some funny numbers. Cool! – user21436 Jan 23 '12 at 23:33
$n=52$ also gives a multiple of $53$, namely $53^2$ – Henry Jan 23 '12 at 23:47
1  
I'll just note that the original problem was $n^2+n+53$. As ncmathsadist pointed out, for the revised problem, the corresponding answer is $n=41$. – Gerry Myerson Jan 24 '12 at 1:31
up vote 1 down vote

n=53, your number is multiple by 53

share|improve this answer
Same as the comment for Gerry! Cool! +1! – user21436 Jan 23 '12 at 23:35
up vote 1 down vote

If you take $n = 41$, it's all over.

share|improve this answer

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.