Are numbers of the form $n^2+n+17$ always prime

Question

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?

Answer 1

Good. Note that both $17$ and $4 \cdot 17 - 1 = 67$ are prime, and the positive binary quadratic form $$ x^2 + x y + 17 y^2 $$ is in a discriminant ($-67$) of only one equivalence class of forms. So, the 1913 theorem of Rabinowitz shows that the values of $n^2 + n + 17$ must be prime for $0 \leq n \leq 15.$ I give a proof of both directions of Rabinowitz (1913) at Is the notorious $n^2 + n + 41$ prime generator the last of its type?

---

Here are the first 100 composite $n^2 + n + 17$ that are not divisible by $17.$ Note that all prime factors $p$ of these must have either $p=67$ or Legendre symbol $(p|67)=1.$

           n       n^2 + n + 17
    1     20         437 = 19 * 23
    2     25         667 = 23 * 29
    3     32        1073 = 29 * 37
    4     36        1349 = 19 * 71
    5     39        1577 = 19 * 83
    6     41        1739 = 37 * 47
    7     43        1909 = 23 * 83
    8     48        2369 = 23 * 103
    9     52        2773 = 47 * 59
   10     54        2987 = 29 * 103
   11     55        3097 = 19 * 163
   12     58        3439 = 19 * 181
   13     61        3799 = 29 * 131
   14     65        4307 = 59 * 73
   15     66        4439 = 23 * 193
   16     69        4847 = 37 * 131
   17     71        5129 = 23 * 223
   18     74        5567 = 19 * 293
   19     77        6023 = 19 * 317
   20     78        6179 = 37 * 167
   21     80        6497 = 73 * 89
   22     83        6989 = 29 * 241
   23     88        7849 = 47 * 167
   24     89        8027 = 23 * 349
   25     90        8207 = 29 * 283
   26     93        8759 = 19 * 461
   27     94        8947 = 23 * 389
   28     96        9329 = 19 * 491
   29     97        9523 = 89 * 107
   30     99        9917 = 47 * 211
   31    100       10117 = 67 * 151
   32    105       11147 = 71 * 157
   33    106       11359 = 37 * 307
   34    107       11573 = 71 * 163
   35    111       12449 = 59 * 211
   36    112       12673 = 19 * 23 * 29
   37    115       13357 = 19^2 * 37
   38    116       13589 = 107 * 127
   39    117       13823 = 23 * 601
   40    122       15023 = 83 * 181
   41    124       15517 = 59 * 263
   42    126       16019 = 83 * 193
   43    131       17309 = 19 * 911
   44    134       18107 = 19 * 953
   45    137       18923 = 127 * 149
   46    138       19199 = 73 * 263
   47    140       19757 = 23 * 859
   48    141       20039 = 29 * 691
   49    143       20609 = 37 * 557
   50    146       21479 = 47 * 457
   51    148       22069 = 29 * 761
   52    150       22667 = 19 * 1193
   53    151       22969 = 103 * 223
   54    157       24823 = 103 * 241
   55    158       25139 = 23 * 1093
   56    160       25777 = 149 * 173
   57    163       26749 = 23 * 1163
   58    167       28073 = 67 * 419
   59    172       29773 = 19 * 1567
   60    176       31169 = 71 * 439
   61    177       31523 = 29 * 1087
   62    178       31879 = 71 * 449
   63    180       32597 = 37 * 881
   64    181       32959 = 23 * 1433
   65    182       33323 = 47 * 709
   66    183       33689 = 59 * 571
   67    185       34427 = 173 * 199
   68    188       35549 = 19 * 1871
   69    189       35927 = 37 * 971
   70    191       36689 = 19 * 1931
   71    192       37073 = 131 * 283
   72    193       37459 = 47 * 797
   73    199       39817 = 29 * 1373
   74    200       40217 = 131 * 307
   75    201       40619 = 151 * 269
   76    205       42247 = 83 * 509
   77    206       42659 = 29 * 1471
   78    207       43073 = 19 * 2267
   79    208       43489 = 157 * 277
   80    209       43907 = 23^2 * 83
   81    210       44327 = 19 * 2333
   82    211       44749 = 73 * 613
   83    212       45173 = 199 * 227
   84    217       47323 = 37 * 1279
   85    218       47759 = 163 * 293
   86    223       49969 = 107 * 467
   87    226       51319 = 19 * 37 * 73
   88    227       51773 = 23 * 2251
   89    228       52229 = 29 * 1801
   90    229       52687 = 19 * 47 * 59
   91    232       54073 = 23 * 2351
   92    234       55007 = 67 * 821
   93    235       55477 = 29 * 1913
   94    239       57377 = 181 * 317
   95    240       57857 = 47 * 1231
   96    241       58339 = 227 * 257
   97    242       58823 = 59 * 997
   98    243       59309 = 127 * 467
   99    245       60287 = 19^2 * 167
  100    247       61273 = 71 * 863
         n         n^2 + n + 17

---

    0          17 = 17
    1          19 = 19
    2          23 = 23
    3          29 = 29
    4          37 = 37
    5          47 = 47
    6          59 = 59
    7          73 = 73
    8          89 = 89
    9         107 = 107
   10         127 = 127
   11         149 = 149
   12         173 = 173
   13         199 = 199
   14         227 = 227
   15         257 = 257
   16         289 = 17^2
   17         323 = 17 * 19
   18         359 = 359
   19         397 = 397
   20         437 = 19 * 23
   21         479 = 479
   22         523 = 523
   23         569 = 569
   24         617 = 617
   25         667 = 23 * 29
   26         719 = 719
   27         773 = 773
   28         829 = 829
   29         887 = 887
   30         947 = 947
   31        1009 = 1009
   32        1073 = 29 * 37
   33        1139 = 17 * 67
   34        1207 = 17 * 71
   35        1277 = 1277
   36        1349 = 19 * 71
   37        1423 = 1423
   38        1499 = 1499
   39        1577 = 19 * 83
   40        1657 = 1657
   41        1739 = 37 * 47
   42        1823 = 1823
   43        1909 = 23 * 83
   44        1997 = 1997
   45        2087 = 2087
   46        2179 = 2179
   47        2273 = 2273
   48        2369 = 23 * 103
   49        2467 = 2467
   50        2567 = 17 * 151

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.