# How many solutions are there to $F(n,m)=n^2+nm+m^2 = Q$?

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$?

-

6
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♦ 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♦ Jun 8 '11 at 18:42

## 1 Answer

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.

-

3
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

2
– 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♦ Jun 8 '11 at 19:27
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 42, "mathjax_display_tex": 7, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9421892166137695, "perplexity_flag": "head"}