# The quadratic form $x^2 + ny^2$ via prime factors

Elementary algebra shows that the product of two numbers in the form $x^2 + ny^2$ again has the same form, since if $p = (a^2 + nb^2)$ and $q = (c^2 + nd^2)$, $$pq = (a^2 + nb^2)(c^2 + nd^2) = (ac \pm nbd)^2 + n(ad \mp bc)^2$$ My question is: Assuming that a number $z$ can be factored into primes of the form $x^2 + ny^2$, does every representation of $z$ in this form arise from repeated applications of this formula to the prime factors?

-
give me a minute, Gerry pointed out that I had missed your actual intent. – Will Jagy Nov 4 '12 at 22:47
Let me know if my second answer is what you wanted, I've got a million of these. – Will Jagy Nov 4 '12 at 23:18

Alright, the answer to the actual question asked is yes, as follows. I am taking a prime $p$ with $\gcd(p,n) = 1.$ Then I am demanding $u^2 + n v^2 = p.$ Next, I am taking some number, composite or prime, call it $Q,$ and demand about $pQ$ rather than $Q$ itself, $$pQ = r^2 + n s^2.$$ First, we get $$\left( \frac{u}{v} \right)^2 \equiv \left( \frac{r}{s} \right)^2 \equiv -n \pmod p.$$ Choose $\pm s$ so that $$\left( \frac{u}{v} \right) \equiv \left( \frac{r}{s} \right) \pmod p.$$ So we have $u s \equiv v r \pmod p,$ or $$-us + vr \equiv 0 \pmod p.$$ Next, $$p^2 Q = (ur + n v s)^2 + n (-us + v r)^2,$$ and so $$Q = \left( \frac{ur + n v s}{p} \right)^2 + n \left(\frac{-us + v r}{p} \right)^2$$ in integers.

Combine this once again with $p = u^2 + n v^2$ and you get back to $pQ = r^2 + n s^2$ as desired.

-

Well, no. It is a fair question, though. Even with class number one, we can begin with $1 + 3 = 4,$ although $x^2 + 3 y^2$ does not represent $2.$ The way Dickson would have talked about this is the imprimitive form of the same discriminant, namely $2 x^2 + 2 x y + 2 y^2.$

Staying with one class per genus, we have $1 + 5 = 6,$ although $x^2 + 5 y^2$ does not represent $2,3.$ This is a different phenomenon called Gauss composition. The trick for this one is that $2 x^2 + 3 y^2$ does represent $2,3,$ and there is a different identity that allows $(2 a^2 + 3 b^2)(2 c^2 + 3 d^2) = x^2 + 6 y^2.$ You should probably be able to find such an identity by hand.

One of the simplest ones where identifying the primes involved becomes a mess is $x^2 + 11 y^2.$ It is a bit of a problem (although solved) to say which primes can be expressed as $x^2 + 11 y^2$ and which by $3 x^2 + 2 x y + 4 y^2,$ among those primes $p$ for which the Jacobi symbol $(-11 | p) = 1.$ But, seeing as the latter form does represent $3,5$ integrally, we are not surprised to see $4 + 11 = 15.$ In this case, you ought to involve the "opposite" form in $(3 a^2 + 2 a b + 4 b^2)(3 c^2 - 2 c d + 4 d^2) = x^2 + 11 y^2.$ The presence of the opposite form is what makes the set (of three "classes") into a group.

Well, that's a start.

-
I'm not sure this speaks to the question which, as I understand it, goes: if $z=pq$, and $p=a^2+nb^2$, and $q=c^2+nd^2$, then must every representation $z=e^2+nf^2$ come from these representations of $p$ and $q$? E.g., $47=6^2+(11)1^2$, $103=2^2+(11)3^2$; if $(47)(103)=r^2+11s^2$, must $r,s$ come from the identity in the original post? – Gerry Myerson Nov 4 '12 at 22:37
@Gerry, I see what you mean. I believe the answer to that is yes, let me think about it. As long as $4n \neq 0 \pmod {pq}.$ – Will Jagy Nov 4 '12 at 22:43
@GerryMyerson, separate answer posted. There are always extra cases, I imagine $n=p$ works out as well but is not currently included. – Will Jagy Nov 4 '12 at 23:22