<s>[INST] $p=a^2+ab+41b^2$ iff $-163$ is a quadratic residue Prove that a prime $p$ can be written as $p=a^2+ab+41b^2$ iff $-163$ is a quadratic residue modulo $p$. 
What I have in mind is something like this: look at $\mathbb{Q}[\sqrt{-163}]$ which has the ring of integers $\mathbb{Z} \left [ \dfrac{1+\sqrt{-163}}{2} \right ]$. Now $p$ is of that form iff $p$ is the norm of an element in the ring of integers. It is well known that the ring of intergers in this case is a PID. However, I cannot tie the fact that -163 has to be a quadratic residue to all of this (in one direction, clearly if $p=a^2+ab+41b^2$ then $4p=(2a+b)^2+163b^2$ so $-163$ has to be a quadratic residue).  Could somebody help me complete a solution along these lines? 
 [/INST] I love the form "$a^2 + ab + 41b^2$" because it helps confuse humans. The fact that $a$ and $b$ are integers is too small a benefit to make this confusion worthwhile.
Setting $$\theta = \frac{1}{2} + \frac{\sqrt{-163}}{2}$$ we see that $(a + b \theta)(c + d \theta) = p$ gives us two solutions to $a^2 + ab + 41b^2 = p$. For example, $\theta (1 - \theta) = 41$ tells us that $0^2 + 0 \times 41 + 41 + 41 \times 1^2 = 41$ and $1^2 + (1 \times -1) + 41 \times (-1)^2 = 41$. However, if we rewrite $a + b \theta$ as $$\frac{m}{2} + \frac{n \sqrt{-163}}{2},$$ the relationship between a number in this domain and its conjugate becomes much easier to see. In fact, $$\left(\frac{m}{2} - \frac{n \sqrt{-163}}{2}\right) \left(\frac{m}{2} + \frac{n \sqrt{-163}}{2}\right) = N,$$ which in this example is the prime $41$ if we set $m = n = 1$: $$\left(\frac{1}{2} - \frac{\sqrt{-163}}{2}\right) \left(\frac{1}{2} + \frac{\sqrt{-163}}{2}\right) = 41.$$
</s>