Find the lowest value of $n$, such that the equation $p^{2}+pq+q^{2}=n$ has only five solutions

Solution 1:

I'm going with $7^4×13=31213$. Three of the solutions are obtained by multiplying the solutions for $637$ by $7^2$:

$637 \rightarrow (4,23)$ thus $31213\rightarrow (28,161)$

$637 \rightarrow (7,21)$ thus $31213 \rightarrow (49,147)$

$637 \rightarrow (12,17)$ thus $31213 \rightarrow (84,119)$

Render the additional factor of $7^2$ as $3^2+(3×5)+5^2$ and use the multiplicative properties of Eisenstein integers to generate exactly two additional, primitive solutions:

$31213 \rightarrow (9,172)$

$31213 \rightarrow (101,103)$

Let us delve more deeply into how those two primitive solutions come about. We have, for $637$ and $49$ respectively:

$637=4^2+(4×23)+23^2$

$49=3^2+(5×3)+5^2$

An Eisenstein integer has the form $a+b\omega $ where $\omega $ is a primitive cube root of unity. The norm of $p-q\omega $ (Note the negative sign) is then $\sqrt{p^2+pq+q^2}$. Thus

$|4-23\omega |=\sqrt{637}$

$|3-5\omega |=\sqrt{49}=7$

Now just multiply the Eisenstein integers , eliminating $\omega ^2$ by rendering it as $-1-\omega$. Then the product is:

$|-103-204\omega |=\sqrt{31213}$

This does not correspond to a positive integer solution for $p$ and $q$ because that requires the integer coefficients to have mixed signs! But we can multiply $-103-204\omega$ by $\omega$ to get

$|101-103\omega |=\sqrt{31213}$

$101^2+(101×103)+103^2=31213$

To get the $(9,172)$ solution we multiply $12-17\omega$ by $5-3\omega$, reversing the order of the $7^2$ decomposition. All other possible multiplications using Eisenstein integers from the solutions for $637$ and $49$ repeat the three nonprimitive solutions obtained directly from $31213=637×7^2$, or the two primitive solutions already proposed.

Solution 2:

All the $\alpha_k$ (the smallest integers with $k$ ways to decompose as $p^2+pq+q^2$ that I have been able to find are divisible by $13$. The answer to the problem is $\alpha_5 = 31213 = 7^4\cdot 13$. The $\alpha_k$ seem to love prime factors of the form $6r+1$ and hate prime factors of the form $6r-1$.

$$\begin{array}{rl} \alpha_2 = & 91 = 7 \cdot 13 \\ \alpha_3 = & 637 = 7^2 \cdot 13 \\ \alpha_4 = & 1729 = 7 \cdot 13 \cdot 19 \\ \alpha_5 = & 31213 = 7^4 \cdot 13 \\ \alpha_6 = & 12103 = 7^2 \cdot 13 \cdot 19\\ \alpha_7 = & 405769 = 7^4 \cdot 13^2 \\ \alpha_8 = & 53599 = 7 \cdot 13 \cdot 19 \cdot 31\\ \alpha_9 = & 157339 =7^2 \cdot 13^2 \cdot 19 \\ \alpha_{10} = & 593047 = 7^4 \cdot 13 \cdot 19\\ \alpha_{11} = & 7^{10}×13 (**)\\ \alpha_{12} = & 375193 = 7^2 \cdot 13 \cdot 19 \cdot 31\\ \alpha_{13} = & 2989441 = 7^2 \cdot 13^2 \cdot 19^2 \\ \alpha_{14} = & 29059303 = 7^6 \cdot 13 \cdot 19 \\ \alpha_{15} = & 7709611 = 7^4 \cdot 13^2 \cdot 19 \\ \alpha_{16} = & 1983163 = 7 \cdot 13 \cdot 19 \cdot 31 \cdot 37\\ \alpha_{17} = & 7^6×13^4 (**)\\ \alpha_{18} = & 4877509 = 7^2 \cdot 13^2 \cdot 19 \cdot 31 \\ \alpha_{19} = & 7^{12}×13^2 (**)\\ \alpha_{20} = & 18384457 = 7^4 \cdot 13 \cdot 19 \cdot 31 \\ \alpha_{21} = & 377770939 = 7^6 \cdot 13^2 \cdot 19 \\ \alpha_{22} = & 146482609 = 7^4 \cdot 13^2 \cdot 19^2 \\ \alpha_{24} = & 13882141 = 7^2 \cdot 13 \cdot 19 \cdot 31 \cdot 37\\ \alpha_{27} = & 92671671 = 7^2 \cdot 13^2 \cdot 19^2 \cdot 31 \\ \end{array} $$

** - expected result based on prime factorizations.

The value given now for $\alpha_9$ lower than that quoted originally; it was verified as having nine positive solutions by exhaustive search. With three distinct prime factor $2^{3-1}=4$ of the nine solutions are primitive, the rest nonprimitive.