Does $8a+5$ ever divide $b^2+8$? For natural $a,b$, does $8a+5$ ever divide $b^2+8$ ?
It doesn't for $b$ up to $10^7$.
Couldn't find congruence obstructions for moduli up to $500$.
$b^2+8$ can be even.

You say you couldn't find a congruence obstruction for moduli up to $500$, but there is such an obstruction to having $-8 \equiv b^2 \bmod 8a+5$, revealed by Jacobi reciprocity. Since $-8$ is a unit modulo $8a+5$, so would be $b$, and therefore using Jacobi symbols we would get $(\frac{-8}{8a+5}) = (\frac{b^2}{8a+5}) = 1$. Positivity of $a$ is used in the meaning of the Jacobi symbol that was just written down and, more importantly, in computational rules for the Jacobi symbol that will now be used.
Since $8a+5\equiv 5 \bmod 8$ we have $(\frac{2}{8a+5}) = -1$, and $(\frac{-1}{8a+5}) = (-1)^{((8a+5)-1)/2} = 1$, so $(\frac{-8}{8a+5}) = (-1)^3 = -1$. This is a contradiction.
