All prime divisors $p \neq 3$ of $a^2+a+1$ are $\equiv 1 \mod 3$. So the desired number is (by chinese remainder theorem) $3^k$ where $k$ is the number of prime divisors of $m$ different from $3$.

ZetaX wrote: All prime divisors $p \neq 3$ of $a^2+a+1$ are $\equiv 1 \mod 3$. So the desired number is (by chinese remainder theorem) $3^k$ where $k$ is the number of prime divisors of $m$ different from $3$. How to use the chinese remainder theorem in this case? Can you show?

Let $f(a)$ be the desired number of solutions $\mod a$. We have to show for coprime integers $a,b$: $f(ab)=f(a)f(b)$. Now let $a_1,a_2,...,a_{f(a)}$ be the solutions $\mod a$, $b_1,b_2,...,b_{f(b)}$ be the solutions $\mod b$. Then for every pair $(a_i,b_j)$ there is a $x , 0\leq x <ab$ with $x \equiv a_i \mod a$ and $x \equiv b_j \mod b$ (that's the point where the chinese remainder theorem is used). But then $x^3 \equiv 1 \mod a$ and $x^3 \equiv 1 \mod b$, so $x^3 \equiv 1 \mod ab$. This gives immediatly $f(ab) \geq f(a) f(b)$. But if $x$ is a solution $\mod ab$, it is a solution $\mod a$ and $\mod b$, so we reach finally $f(ab)=f(a)f(b)$.