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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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

Furthermore, how can we prove/disprove this?

Oh, sorry, I meant 41...

share|cite|improve this question

marked as duplicate by Jonas Meyer, Ivo Terek, RecklessReckoner, dustin, Ahaan S. Rungta Jan 19 '15 at 2:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

you'd better think before – Evgeny Savinov Jan 23 '12 at 23:33
@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
@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
@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
@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
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|cite|improve this answer
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
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

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

share|cite|improve this answer

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

share|cite|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

n=53, your number is multiple by 53

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

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

share|cite|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
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

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