Are numbers of the form $n^2+n+17$ always prime Someone claimed that a number, multiplied by the number after it plus 17 is always prime, and showed several cases. I'm not a complete amateur in Number Theory, and I know that $17*18+17=17*19$, so it does not work for $n\equiv0(\mod17)$ but does it always work for other $n$ values? If not, can someone give me a counter example that I can show that person so they can correct their statement?
 A: Another counterexample: look at modulo $23$ arithmetic.  We have
$$n^2+n+17\equiv n^2+n-6\pmod{23}$$
$$n^2+n-6=(n+3)(n-2)$$
Therefore, $n^2+n+17\equiv0\pmod{23}$ when $n\equiv2$ or $20\pmod{23}$.
Following the same method, one can find multiples of $19,29,37,47,$ etc.
A: This does not hold in a strong sense. Not only are there no polynomials generating only primes (or only primes outside some nontrivial arithmetic progression), but for any given polynomial the fraction of prime terms from 0 to N tends to 0 as N increases without bound.
Will's list shows that there are some composites up to 50, about a quarter of the list, but if you go further you'll find 50% composite, 75% composite, 99.9% composite -- as high as you like.
The precise asymptotic fraction which are prime is not known but there is a general conjecture of Bateman, Horn, and Stemmler which addresses this in detail.
A: Another way to cook up counterexamples:Take $n \equiv 1$ (mod $19$) and $n \geq 20.$  Then $n^{2}+n+17 \equiv 0$ (mod $19$),  but $n^{2} +n + 17 > (n^{2} +16) >19,$ so $n^{2} + n + 17$ is not prime. More generally, $x^{2}+x+17$ is strictly increasing on $(0, \infty),$ so if we find an integer $m > 0$ such that $m^{2}+m +17 = q$ is a prime, then whenever $n = m+tq$ for a positive integer $t,$ we have $n^{2}+n +17 \equiv 0$ (mod $q$), but $n^{2}+n+17 >q,$ so $n^{2} + n + 17$ is not prime. For example, this explains what happens in Will Jagy's table for $n = 10$ and $n = 25,$ looking at $m =1, (q =19)$ and $m =2, (q = 23) $ respectively.
A: There are plenty of numbers besides multiples of $17$ that fail to give primes in that formula.
Even with "handicaps" like the one you give, there's just no polynomial that always gives primes. according to Mathworld, Legendre proved this long, long ago: http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
See Sloane's A007636.
