# Primes of the form $p=x^2+ny^2$ – Why are congruence given mod $4n$

I’m currently reading Cox’s Primes of the Form $$x^2+ny^2$$, and when giving congruences regarding forms of $$x^2+ny^2$$, they are given $$\pmod{4}$$. E. g., when stating the primes that satisfy $$\left(\dfrac{-7}p\right)=1$$, it is stated $$p \equiv 1,9,11,15,23,25 \pmod{28}$$. But this is equivalent to $$p \equiv 1,2,4 \pmod 7$$, which is a much more natural answer as this is what quadratic reciprocity immediately reveals.

I assume this was done for a reason, as when the solutions to $$p=x^2+ny^2$$ are discussed, they are always $$\pmod{4n}$$. E. g., if $$p=x^2+5y^2$$, $$p \equiv 1,9 \pmod{20}$$. On page 13, it says that:

The reciprocity step can be restated as the following question: is there a congruence $$p \equiv a,b,\cdots \pmod{4n}$$ which implies $$\left(\dfrac{-n}p\right)=1$$ when $$p$$ is prime?

But I don’t understand why it is necessary to use $$4n$$ rather than $$n$$. I’m sorry if this is a silly question but I feel that it’s essential to understand before continuing. Thanks for any help in advance.

The mod $$4$$ relation comes from the minus sign: from standard properties, $$\left(\frac{-7}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{7}{p}\right)$$ and it is well known that $$\left(\frac{-1}{p}\right)=1 \Leftrightarrow p \equiv 1 \mod{4}$$. One then applies the main theorem that allows you to connect $$\left(\frac{7}{p}\right)$$ with $$\left(\frac{p}{7}\right)$$ but you should note that this again depends on $$p \mod{4}$$.

In particular $$\left(\frac{7}{p}\right)=\left(\frac{p}{7}\right)$$ if and only if $$p \equiv 1 \mod{4}$$. However, this is the same condition we had before so actually $$\left(\frac{-7}{p}\right)=\left(\frac{p}{7}\right)$$ but we didn't know without checking first.

However I should remark at this point that if $$n \equiv 1 \mod{4}$$ is prime then $$\left(\frac{-n}{p}\right) \neq \left(\frac{p}{n}\right)$$ and this mod 4 relation is important.

A more general explanation is that this comes from factorising $$p=x^2+ny^2$$ as $$(x+i\sqrt{n}y)(x-i\sqrt{n}y)$$. To guarantee this splitting, you want both $$i=\sqrt{-1}$$ and $$\sqrt{n}$$ to be elements mod $$p$$ and $$i$$ is an element mod $$p$$ exactly when $$p \equiv 1 \mod{4}$$. This is sufficient but by no means necessary; in the case $$n=7$$ above, we have $$\sqrt{-n}$$ is an element mod $$p$$ in those cases, but you'll find that $$\sqrt{n}$$ and $$i$$ are not.

• Is there any reason why the fractions are in parentheses? Apr 21, 2020 at 10:07
• They're not fractions: this is notation for legendre symbols. See here en.wikipedia.org/wiki/Quadratic_reciprocity Apr 21, 2020 at 10:08
• Thank you for responding! Apr 21, 2020 at 10:09
• 8 does not need to be on the list since $p$ is prime Apr 21, 2020 at 11:49
• @häxq thanks I thought I was missing something; I just lifted the residue classes without thinking about coprimality. I've edited accordingly. Apr 21, 2020 at 14:43