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

Question

So, I know this is only possible whenever $d$ is a square $\pmod{4\cdot |n|}$, but can that be simplified any further?

As an example, if I am given that $d=-39$ and $n=500$, this reduces to solving $x^2 \equiv -39 \pmod{500}$, but how can I find concrete $x$'s that satisfy the equation? What if the $x$'s have to be prime?

Answer 1

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 = 31\mod 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.