Determine if $n$ could be represented by a quadratic form of discriminant $d$

OK, let's do the example $x^2 equiv -39 mod 500$. $500 = 4 times 5^3 $ so we'll solve it mod $4$ and mod $5^3$, and use the Chinese Remainder Theorem.

$-39 equiv 1 mod 4$, and $x^2 equiv 1 mod 4$ iff $x$ is odd, i.e. $x equiv 1$ or $3 mod 4$.

$-39 equiv 1 mod 5$, and $x^2 equiv 1 mod 5$ iff $x equiv 1$ or $4 mod 5$.

If $x = 1 + 5 y$, $x^2 equiv 1 + 10 y equiv -39 mod 25$ iff $2 y equiv 3 mod 5$ iff $y equiv 1 mod 5$. If $x = 1 + 5 cdot 1 + 5^2 cdot z = 6 + 5^2 cdot z$, $x^2 equiv 6^2 + 2 cdot 6 cdot 5^2 z equiv 36 + 50 z equiv -39 mod 125$ iff $50 z equiv 50 mod 125$ iff $z equiv 1 mod 5$. Thus $x equiv 1 + 5 cdot 1 + 5^2 cdot 1 = 31mod 125$.

Similarly, corresponding to $x equiv 4 equiv -1 mod 5$ we find $x equiv -31 equiv 94 mod 125$.

Now for Chinese Remainder. There are $4$ cases to consider:

1. If $x equiv 1 mod 4$ and $x equiv 31 mod 125$, $x equiv 281 mod 500$.
2. If $x equiv 1 mod 4$ and $x equiv 94 mod 125$, $x equiv 469 mod 500$.
3. If $x equiv 3 mod 4$ and $x equiv 31 mod 125$, $x equiv 31 mod 500$.
4. If $x equiv 3 mod 4$ and $x equiv 94 mod 125$, $x equiv 219 mod 500$.

So the solutions mod $500$ are $281, 469, 31$ and $219$.

Each of these four values mod $500$ should correspond to infinitely many primes. The simplest thing to do is to check $281 + 500 k$, $461 + 500 k$, $31 + 500 k$, $219 + 500 k$ for each integer $k$ from $0$ until we find as many primes as we want. As it happens, all but $219$ turn out to be prime for $k=0$, while $219 + 500 = 719$ is prime.