Unable to find solution for $a^2+b^2-ab$, given $a^2+b^2-ab$ is a prime number of form $3x+1$

Question

I have a list of prime numbers which can be expressed in the form of $3x+1$. One such prime of form $3x+1$ satisfies the expression: $a^2+b^2-ab$.

Now I am having list of prime numbers of form $3x+1$ (i.e., $7,19 \ldots$). But I am unable to find the $a$ and $b$ which satisfy the above expression.

Thanks for your help in advance.

Answer 1

Use the identity $a^3+b^3=(a+b)(a^2-ab+b^2)$, and note that, by Little Fermat, $x^3\equiv x\mod 3$, so $a^3+b^3\equiv a+b \mod3$. Hence, if $a+b\not\equiv 0\mod 3$, necessarily $a^2-ab+b^2\equiv 1\mod3$.

Now suppose you've found $a$ and $b$ such that $a^3+b^3$ is the product of two primes. Then one of them will be congruent to $1\bmod 3$, and have the required form.

Computing some values yields $1^3+4^3=(1+4)(1^2-1\cdot 4+4^2)=5\cdot 13$. Thus $13$ is a solution.

Answer 2

How about the following? $$(-2)^2+1^2-(-2)\cdot 1=7=3\cdot 2+1$$