Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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))$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.