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

Let $n,m$ be two positive integers, we consider: $$F(n,m)=n^2+nm+m^2$$

Let $Q$ be one value reach by $F(n,m)$.

How many different pairs $(n,m)$ verify $F(n,m)=Q$?

share|cite|improve this question
The trick in this instance is that $n^2+nm+m^2$ is the norm in the ring $\mathbb{Z}[\omega]$ where $\omega=\frac{1+\sqrt{-3}}2$. Then $N(n+m\omega)=n^2+nm+m^2$. Since $\mathbb{Z}[\omega]$ is a unique factorization domain, you get results like the result for the sum of two squares. – Thomas Andrews Jun 8 '11 at 17:46
@Eric and Ray: Sorry about my erroneous answer; I was too quick to "jump the gun" and as I pursued the problem after posting, I realized I overlooked the restriction to positive m, n...and further, I realized there are far more solutions than my erroneous post revealed. – amWhy Jun 8 '11 at 17:47
@Thomas Andrews: That is an excellent point! I wish had seen that comment before typing my answer. – Eric Naslund Jun 8 '11 at 18:35
@Amwhy: It happens to all of us, no worries. (I have jumped the gun like this many times!) – Eric Naslund Jun 8 '11 at 18:42
up vote 11 down vote accepted

As it turns out, we can give a complete answer to this question. The exact number of solutions depends on the prime factorization of $Q$ Specifically, it is a function of the exponents of the prime factors which are congruent to $1$ mod $3$, with the condition that all the factors congruent to $2$ modulo $3$ have their prime factors appear with even multiplicity.
Note: I have not yet provided a proof, the result that primes of the form $1+3k$ can be represented is a theorem of Jacobi.

Let $$Q=\prod_i q_i^{\alpha_i} \prod_i p_i^{\beta_i}$$ where the $q_i$ are $1$ mod $3$ and the $p_i$ are $2$ mod $3$. Our equation $n^2+nm+m^2$ has solutions if and only if each $\beta_i$ is even.

Proof: Take the equation modulo $3$. By case analysis for $n,m$ the right hand side cannot be congruent to $2$, and hence the statement follows.

Remark: Notice the following similarity to the sum of squares problem (points on a circle).

The Answer: Suppose that as before $$Q=\prod_i q_i^{\alpha_i} \prod_i p_i^{\beta_i}$$ where the $q_i$ are $1$ mod $3$ and the $p_i$ are $2$ mod $3$. Suppose as well that all of the $\beta_i$ are even. (Otherwise we can have no solutions)

Let $$B=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1).$$ Then the number of non-negative integer solutions to $$m^2+mn+n^2=Q$$ is exactly $$\left\lceil\frac{B}{2}\right\rceil.$$
(Again notice the similarity to the sum of squares function)

In particular, if $l(n)$ is the number of representations where $n,m$ are any integers, (that is positive or negative) then $$l(n)=2B.$$

Hope that helps.

share|cite|improve this answer
This is a very nice answer. One comment: I'm not sure why you're diagonalizing -- you don't seem to use it anywhere. More fundamentally, the given quadratic form is the norm form of the maximal order of $\mathbb{Q}(\sqrt{-3})$, whereas $x^2 + 3y^2$ is the norm form of the nonmaximal order $\mathbb{Z}[\sqrt{-3}]$, which is not a UFD. So in fact if you wanted to study the form $x^2 + 3y^2$ you would do it by comparing to $x^2 + xy + y^2$, not the other way around. Note also that even without the change of variables you are looking for lattice points on an ellipse. – Pete L. Clark Jun 8 '11 at 18:45
Well, just to be clear, $\mathbb{Z}[\sqrt{-3}]$ is not a UFD: see e.g. Section 3 of for some commentary. (Note also that the quadratic form cannot be diagonalized over $\mathbb{Z}$, only over $\mathbb{Q}$.) – Pete L. Clark Jun 8 '11 at 19:11
@Pete: Ok, thanks for the note! I don't know why I thought it wasn't. – Eric Naslund Jun 8 '11 at 19:27

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.