Smallest prime that divides $n^2+5n+23$ Find the smallest prime that divides $n^2+5n+23$ for some integer $n$. I thought taking all primes less than 29 one by one and then solving the equations and then some manipulation. (Like $n^2+5n+23=2k$). But it didn't help. What else can I do?
 A: If you are unfamiliar with the theory of quadratic residues, then you need to do a bit more work. To exclude the possibility of a prime $p$ from occurring as a factor, you need to test it with all the cases $n=0,1,2,\ldots,p-1$. Do you see why this suffices?

It is easier with a bit of theory of quadratic residues. I use the properties  of the Legendre symbol $\left(\frac a p\right)$ that is $+1$ if $a$ is a QR modulo $p$ and $-1$ if not. 
We can use the "observation" that, given a prime $p$, there exists an integer $n$ such that $p\mid n^2+5n+23$ if and only if the equation $n^2+5n+23=0$ has a solution in the field $\Bbb{Z}_p$ if and only if the discriminant
$$
D=5^2-4\cdot23=-67
$$
is a quadratic residue modulo $p$. This works whenever $p$ is odd, and the case $p=2$ is easy to handle.
Split into two cases.
I) $p$ congruent to $1$ modulo $4$: Here we know that $\left(\frac{-1}p\right)=1$, so we want to know, if $\left(\frac{67}p\right)=1$.
$$
\begin{aligned}
\left(\frac{67}5\right)&=\left(\frac{2}5\right)=-1,\\
\left(\frac{67}{13}\right)&=\left(\frac{2}{13}\right)=-1,\\
\left(\frac{67}{17}\right)&=\left(\frac{67-3\cdot17}{17}\right)=\left(\frac{4^2}{17}\right)=1,\\
\end{aligned}
$$
so $p=17$ is the smallest possible factor. When evaluating $\left(\frac 2p\right)$ use either brute force testing or the appropriate extension of the law of quadratic reciprocity.
II) $p$ congruent to $3$ modulo $4$: Here we know that $\left(\frac{-1}p\right)=-1$, so we want to know, if $\left(\frac{67}p\right)=-1$.
$$
\begin{aligned}
\left(\frac{67}3\right)&=\left(\frac{1}3\right)=1,\\
\left(\frac{67}{7}\right)&=\left(\frac{4}{4}\right)=1,\\
\left(\frac{67}{11}\right)&=\left(\frac{67-6\cdot11}{11}\right)=\left(\frac{1}{11}\right)=1,\\
\end{aligned}
$$
so $p=3,7,11$ cannot occur as prime factors. The next prime in this residue class is $p=19$, which is larger than the smallest prime factor $17$ from case I.
So seventeen it is.

A: Let's have a look at this systematically. It is trivial that $n^2+5n+23$ is odd, so the prime $2$ is out of the picture.

A general observation about quadratic equations modulo $p$
If $n^2+an+b\equiv 0$ modulo some prime $p$ - say for the integer $r$ then $$(n-r)(n+a+r)=n^2+an-r^2-ar\equiv n^2+an+b$$ (because $b\equiv -r^2-ar$) so that the equation has a factorisation modulo $p$.
So it makes sense to talk of a root $r$ mod $p$ and this is always associated with a factorisation of the quadratic. (More general cases can be shown)

Now, since $2$ is out of the picture, multiply by $4$ to work with $4n^2+20n+92=(2n+5)^2+67$, which has a root modulo an odd prime $p$ if and only if $-67$ is a square mod $p$.
Then we test primes. We have $-67 \equiv 2 \bmod 3; 3 \bmod 5; 3\bmod 7; 10\bmod 11 \dots$ or use quadratic reciprocity.
A: This is not a complete answer, but instead provides some evidence that there won't be a simple solution to this problem. Running FactorInteger[n^2 + 5*n +23] up to $n = 25$ in Mathematica yields the following results.
$$\begin{array}{c|l}
  n  & n^2 + 5n +23 \\\hline
  1  & 29  = 29 \\
  2  & 37  = 37 \\
  3  & 47  = 47 \\
  4  & 59  = 59 \\
  5  & 73  = 73 \\
  6  & 89  = 89 \\
  7  & 107 = 107 \\
  8  & 127 = 127 \\
  9  & 149 = 149 \\
  10 & 173 = 173 \\
  11 & 199 = 199 \\
  12 & 227 = 227 \\
  13 & 257 = 257 \\
  14 & 289 = 17^2 \\
  15 & 323 = 17\times19 \\
  16 & 359 = 359 \\
  17 & 397 = 397 \\              
  18 & 437 = 19\times23 \\
  19 & 479 = 479 \\
  20 & 523 = 523 \\
  21 & 569 = 569 \\
  22 & 617 = 617 \\
  23 & 667 = 23\times29 \\
  24 & 719 = 719 \\
  25 & 773 = 773 \\
\end{array}$$
A: Hint: You can change 23 to 19 + 4 so it will become $(n+1)(n+4)+19$ 
btw, the answer is not 19
