In an attempt to get to grips with algebra for a course I intend to follow, I was working through a bunch of exercise sheets. A series of questions got me wondering:
Given an integer $n$, is there a general method (or collection of methods) to tell which primes $p$ are of the form $p=x^2+n\cdot y^2$? Here $x$ and $y$ should also be integers.
For example, for $n=2$ these are precisely the primes $p\equiv1,2,3\pmod{8}$. For $n=5$ (for example) all such primes are congruent to $1$ or $9$ modulo $20$, but I'm unable to prove (or even guess) whether all primes $p\equiv1,9\pmod{20}$ are of this form. My proofs can't seem to avoid the rings $\Bbb{Z}[\sqrt{-n}]$, which makes me think this could related to class field theory, which I think is beyond my grasp (for now). Is there an 'easy' solution to this problem?
well, no. if you pick a discriminant of binary quadratic forms, call it $\Delta,$ and you have an odd prime $p$ that does not divide $\Delta,$ finally $(\Delta|p)= 1,$ then there is some form of that discriminant that represents the prime. If the class number is larger than one, that may not be the principal form. To find the form that works, see How to find a quadratic form that represents a prime?
Usual example: discriminant $-108.$ Every prime $p \equiv 1 \pmod 3$ is represented by some form, out of $x^2 + 27 y^2,$ $4 x^2 + 2 xy + 7 y^2,$ $4 x^2 - 2 xy + 7 y^2.$ The last two represent the same numbers, of course, but this way you get the class group. How can you tell? Well, given $p \equiv 1 \pmod 3,$ if there exists a solution to $u^3 \equiv 2 \pmod p,$ then we can write $p = x^2 + 27 y^2.$ If not, we have $p =4 x^2 \pm 2 xy + 7 y^2.$ Indeed, $31 \equiv 1 \pmod 3,$ and $$ 4^3 = 64 = 62 + 2 \equiv 2 \pmod {31}, $$ from which we know we will be able to find $$ 31 = 4 + 27 = 2^2 + 27 \cdot 1^2 $$
Let's see, the cubes $\pmod 7$ are $\pm 1,$ easy enough to confirm by hand. Two is not a cube, $7$ cannot be written as $x^2 + 27 y^2,$ but we can write it as $4x^2 + 2 xy + 7 y^2$ with $x=0,y=1.$ Cubes $\pmod {13}$ are $1,5,8,12,$ no $2,$ and we can write $13$ as $4x^2 + 2 xy + 7 y^2$ with $x=1,y=1.$ Or as $4x^2 - 2 xy + 7 y^2$ with $x=1,y=-1.$