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.
Every prime of the form $3k+1$ is expressible as $u^2 + 3v^2$ with $\gcd(u,v)=1$ in precisely one way.
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.
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.
Solution 1:
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 $a \equiv b \ ({\rm mod} \ 4)$ or $a \equiv -b \ ({\rm mod} \ 4)$. In the first case we have $\frac{N}{4}=Q(\frac{a+3b}{4},\frac{a-b}{4})$ and in the second we have $\frac{N}{4}=Q(\frac{a-3b}{4},\frac{a+b}{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))$.