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

Mathematics Asked by jibber032394 on March 4, 2021

So, I know this is only possible whenever $$d$$ is a square $$pmod{4cdot |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?

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.

Answered by Robert Israel on March 4, 2021

Get help from others!