Prime Generating Function 2

I got the idea from Barry Cipra .

Because $3n^2 + 3n + 23 = 3n(n+ 1) + 23$ is divisible by $23$ when $n=22$ , the upper bound of the answer is $22$ . And I'm going to prove that $n=22$ is the solution by showing that no smaller values of $n$ satisfy the condition.

Since $12(3n^2+3n+ 23) = (6n+3)^2 + 267$ , we just need to show that $-267$ is a quadratic non-residue mod odd primes less than $23$ but bigger than $3$ . A trivial substitution of $n=3$ shows that it's prime.

If $p | 3n^2 + 3n + 23$ , then $(6n+3)^2 + 267 \equiv 0 \pmod p$ , which means that $-267$ is a square modulo $p$ . When $n=23, 3n^2 + 3n + 23 = 1679$ , so if any of them were composite, it would have a prime factor less than $\sqrt{1679} \approx 40.97$ .

That prime factor would have to be odd, since it's clear that $3n^2 + 3n + 23$ is always odd, this would require $-267$ to be a quadratic residue for some odd prime less than $40$ but bigger than $n=3$ . So it suffices to compute the Legendre symbol $\left( \frac{-267}p \right)$ for $p=5,7,11,13,17,19,23,29,31,37$ and show that it's $-1$ for all cases.

With the help of law of quadratic reciprocity.

when $p=5$ , $\left( \frac{-267}{5} \right) \equiv \left( \frac{3}{5} \right)\equiv 3^{ \frac{5-1}2 } \equiv -1$ .

when $p=7$ , $\left( \frac{-267}{7} \right) \equiv \left( \frac{-1}{7} \right) \equiv -1$ .

when $p=11$ , $\left( \frac{-267}{11} \right) \equiv \left( \frac{-3}{11} \right)\equiv -\left( \frac{3}{11} \right)\equiv \left( \frac{11}{3} \right)\equiv \left( \frac{-1}{3} \right) \equiv -1$ .

when $p=13$ , $\left( \frac{-267}{13} \right) \equiv \left( \frac{-7}{13} \right)\equiv -\left( \frac{7}{13} \right) \equiv-\left( \frac{13}{7} \right) \equiv - \left( \frac{1}{7} \right) \equiv -1$ .

when $p=17$ , $\left( \frac{-267}{17} \right) \equiv \left( \frac{-12}{17} \right)\equiv \left( \frac{5}{17} \right) \equiv \left( \frac{17}{5} \right)\equiv \left( \frac{2}{5} \right) \equiv 2^{\frac42} \equiv -1$ .

when $p=19$ , $\left( \frac{-267}{19} \right) \equiv \left( \frac{-1}{19} \right)\equiv (-1)^{\frac{19-1}2} \equiv -1$ .

when $p=23$ , $\left( \frac{-267}{23} \right) \equiv \left( \frac{-6}{23} \right) \equiv \left( \frac{17 }{23} \right) \equiv \left( \frac{23}{17} \right) \equiv \left( \frac{6}{17} \right) \equiv 6^8 \equiv 2^4 \equiv -1$ .

when $p=29$ , $\left( \frac{-267}{29} \right) \equiv - \left( \frac{23}{29} \right) \equiv 23^{14} \equiv -23^{14} \equiv -6^{14} \equiv -7^7 \equiv -1$ .

when $p=31$ , $\left( \frac{-267}{31} \right) \equiv \left( \frac{12}{31} \right)\equiv \left( \frac{3}{31} \right) \equiv - \left( \frac{31}{3} \right) \equiv -1$ .

when $p=37$ , $\left( \frac{-267}{37} \right) \equiv -\left( \frac{8}{37} \right)\equiv \left( \frac{29}{37} \right)\equiv \left( \frac{37}{29} \right)\equiv \left( \frac{8}{29} \right)\equiv \left( \frac{2}{29} \right)\equiv 2^{14} \equiv 3^2 \cdot 16 \equiv -1$ .

Hence, we have shown that no prime numbers less than $40$ divide the expression, thus $22$ is the smallest such integer.