# Integers expressible in the form $x^2 + 3y^2$

First of all, I am very thankful to this site. I just came to know this site by google. I have seen some number theory question on this site. The discussion between learner and author is quite good and interesting. I would like to know the proof of following questions. If any one answered, I am very grateful of them.

1. Every prime of the form $3k+1$ is expressible as $u^2 + 3v^2$ with $\gcd(u,v)=1$ in precisely one way.

2. The general primitive solution in integers of the equation $x^2 + 3y^2 = N^3$ for odd $N$ is given by $x = u(u^2 - 9v^2)$ and $y = 3v(u^2 - v^2)$ where $u$ and $v$ are co-prime integers.

3. If an integer is representable in the form $a^2 + 3b^2$ with $\gcd(a,3b)=1$, then its only odd prime factors are of the form $p = 3k+1$.

Once again thanks for all team members of this site.

-
In your first question, what is $a$ and $b$? You are only talking about a prime $p$ and some integers $u,v$ –  Hassan Muhammad Oct 29 '11 at 6:44
Have you tried anything yourself? If $p$ is odd and prime and not $3k+1$, what is it? and what would the implications be of such a prime dividing $a^2+3b^2$? in particular, what would it say about the quadratic character of $-3$? Have you seen the analogous theorems proved for $u^2+v^2$ and primes $p=4k+1$? If so, can you see how to tweak them to the current situation? –  Gerry Myerson Oct 29 '11 at 8:07
yes, I tried. But, I couldn't get. –  mathew Oct 29 '11 at 8:49
See also this related question. –  Bill Dubuque Jan 3 '12 at 23:19

Your questions are actually a special case of a fascinating topic in number theory, already studied by Euler and Lagrange. "Primes of the form x^2+ky^2" by David Cox is a very good reference on the subject. Now to answer your questions : let $Q(x,y)=x^2+3y^2$.

Lemma 1. Let $p$ be an odd prime. Then $-3$ is a square modulo $p$ iff $p$ is congruent to 1 modulo 3.

Proof of lemma 1. $-3$ is a square iff $x^2+3$ has a root iff $y^2-y+1$ has a root (set $y=\frac{x+1}{2}$). Now $y^2-y+1$ is the sixth cyclotomic polynomial. So $-3$ will be a square iff a primitive sixth root of unity exists in ${\mathbb Z}_p$, iff some element in ${\mathbb Z}_p^*$ has (multiplicative) order $6$, iff 6 divides the order of ${\mathbb Z}_p^*$ (because ${\mathbb Z}_p^*$ is cyclic). Now the order of ${\mathbb Z}_p^*$ is exactly $p-1$, so that this amounts to $p \equiv 1 \ ({\rm mod} \ 6)$ as desired.

Now we can show §3. Let $p$ be an odd prime diving $a^2+3b^2$ with ${\rm gcd}(a,b)=1$. Then $p$ is coprime to both $a$ and $b$, so $\frac{a}{b}$ exists in ${\mathbb Z}_p^*$ and it is a square root of $-3$. By lemma 1, we have that $p \equiv 1 \ ({\rm mod} \ 3)$ as wished.

Lemma 2. Let $N$ be a integer of the form $Q(x,y)$. If $2$ divides $N$, then $\frac{N}{4}$ is also an integer of the form $Q(x,y)$. If a prime $p=Q(x_0,y_0)$ divides $N$ then $\frac{N}{p}$ is also an integer of the form $Q(x,y)$.

Proof of lemma 2. Suppose that $2$ divides $N=Q(a,b)$. Then $a$ and $b$ are both even or both odd. If they are both even then $\frac{N}{4}=Q(\frac{a}{2},\frac{b}{2})$. If they are both odd then either $b \equiv a \ ({\rm mod} \ 4)$ or $b \equiv -a \ ({\rm mod} \ 4)$. In the first case we have $\frac{N}{4}=Q(\frac{b+3a}{4},\frac{b-a}{4})$ and in the second we have $\frac{N}{4}=Q(\frac{b-3a}{4},\frac{b+a}{4})$. Now suppose that a prime $p=Q(x_0,y_0)$ divides $N=Q(a,b)$. The product $(-y_0a+x_0b)(-y_0a-x_0b)=y_0^2a^2-x_0^2b^2$ is $0$ modulo $p$, so (replacing $b$ with $-b$ if needed) we may assume that $-y_0a+x_0b \equiv 0 \ ({\rm mod} \ p)$. Set $a'=\frac{x_0a+3y_0b}{p}$ and $b'=\frac{-y_0a+x_0b}{p}$. Then $a'$ and $b'$ are both integers and $\frac{N}{p}=Q(a',b')$. This finishes the proof of lemma 2.

Let us now show §1, by induction on $p$. Let $p$ be an odd prime such that $p \equiv 1 \ ({\rm mod} \ 3)$. Then there is a $v$ with $v^2 \equiv -3 \ ({\rm mod} \ p)$ by lemma $1$. So $p$ divides $N=v^2+3\times 1^2$, and by §3 all the primes factors of $N$ are congruent to $1$ modulo $3$ (or equal to $2$). So by the induction hypothesis, all those primes are of the form $Q(x,y)$. Using lemma 2 several times, we can remove all the factors in $N$ other than $p$ and we finally obtain that $p$ is of the form $Q(x,y)$. This decomposition is unique up to signs, because if $p=Q(x,y)=Q(x',y')$, then (as in the proof of lemma 2), we may assume that $-yx'+xy' \equiv 0 \ ({\rm mod} \ p)$. Set $a'=\frac{xx'+3yy'}{p}$ and $b'=\frac{-yx'+xy'}{p}$. Then $a'$ and $b'$ are both integers and $1=Q(a',b')$, so $a'=\pm 1, b'=0$ and hence $x'=\pm x, y'=\pm y$.

Lemma 3. Any product of integers of the form $Q(x,y)$ is again of this form.

Proof of lemma 3. $Q(x,y)Q(x',y')=Q(xx'-3yy',xy'+yx')$ (multiplicativity of norms).

Finally, let us show §2. If $N=Q(x,y)$ is odd then all its prime factors are odd, so by §3they are all congruent to $1$ modulo $3$. Then by §1 they are all of the form $Q(x,y)$. So their product is also of this form by lemma 3 : $N=Q(u,v)$. We deduce $N^2=Q(u,v)Q(u,v)=Q(u^2-3v^2,2uv)$ and $N^3=Q(u,v)Q(u^2-3v^2,2uv)=Q(u(u^2-3v^2)-3v(2uv),v(u^2-3v^2)+u(2uv))= Q(u(u^2-9v^2),3v(u^2-v^2))$.

-
well, Thank you so much! If you don't mind, how can we prove the following results. –  mathew Oct 29 '11 at 18:53
! I am once again thankful to your contribution and very neat presentation. Can you help me in these questions, which has link to the above solutions. (1) If we let [n\p] equal +1 or -1 accordingly as n is or is not a square (mod p), and if m,n are residues co-prime to p, then [mn\p] = [m\p][n\p] and (2) If N is an integer of the form a^2 + 3b^2, and if the prime p = c^2 + 3d^2 divides N, then there exist integers u,v such that N/p = u^2 + 3v^2 and of N is given by evaluating the product. (p)(N/p) = (u^2 + 3v^2)(c^2 + 3d^2) using Fibonacci's formula. –  mathew Oct 29 '11 at 18:56
! to be frankly, I am so happy with your solutions and it is really worth for me. Thank you....soooooooo much sir. –  mathew Oct 29 '11 at 18:57