From the preceding, it should be clear that, as far as just determining whether a solution exists, all we need to examine is prime moduli. Everything else is taken care of by previous work.
But it's not like \(x^2+k\) is the only quadratic game in town. What about other quadratics?
It turns out that we can use something you are already familiar with to reduce the whole game to the following question:
For what primes \(p\) is there a solution to \(x^2\equiv k\text{ mod }(p)\)?
Let's look at general quadratic congruences. The Sage function solve_mod works, if a little naively.
This shows that \(x^2-2x+3\equiv 0\) mod (9) has two solutions. But how might I solve a general quadratic congruence?
The key is completing the square! \[x^2-2x+3=\left(x^2-2x+\left(\frac{2}{2}\right)^2\right)+3-\left(\frac{2}{2}\right)^2=(x-1)^2+2\, ,\] so \[(x-1)^2\equiv -2\text{ mod }(n)\] is the general congruence I want to solve. Assuming I have a square root \(s\) of \(-2\) mod (\(n\)), I just do \(s+1\) and I'm done! Let's try this for a few different \(n\), including of course \(n=9\).
Should you not particularly enjoy completing the square, here is the basic idea. The key thing to keep in mind is that we do not actually divide by \(2a\), but instead multiply by \((2a)^{-1}\).
So to solve, we'll need that \(2a\) is a unit (such as if \(n\) is odd), and then to find all square roots of \(b^2-4ac\) in \(\mathbb{Z}_n\).
Then the solution to \[ax^2+bx+c\equiv 0\text{ mod }(n)\] is actually \[x\equiv(2a)^{-1}(s-b)\text{ mod }(n)\text{, where }s^2\equiv b^2-4ac\text{ mod }(n)\] which in particular means that \[gcd(2a,n)=1\text{ must be true and that }s^2\equiv b^2-4ac\text{ must have a solution.}\]
Let's do all this with \(x^2+3x+5\equiv 0\) mod(\(n\)). Notice that \(b^2-4ac=9-20=-11\), so this equation does NOT have a solution over the integers, or indeed over the real numbers. Does it have a solution in \(\mathbb{Z}_n\) for some \(n\), though?