Let $m=-3^ka$, and $p\mid 3^{3k}a^2+1$, then if $k$ is odd $\genfrac {(} {)} {} {} {-3}{p} = 1\to p\equiv 1\mod 3\to \exists n: \ p \mid n^2+3$.

This was my problem. Very nice solution it doesn't work however for the natural generalization. I've posted it here: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=423699

Rust wrote: Let $m=-3^ka$, and $p\mid 3^{3k}a^2+1$, then if $k$ is odd $\genfrac {(} {)} {} {} {-3}{p} = 1\to p\equiv 1\mod 3\to \exists n: \ p \mid n^2+3$. How do you prove that this procedure produces infinitely many prime numbers $p$ ? It might be possible that, when $k$ describes the set of all odd integers, you still get only finitely many prime factors... (Note that I seriously doubt it) Moreover, if you fix this point, you still do not need the reciprocity law that you impicitly used when saying $\genfrac {(} {)} {} {} {-3}{p} = 1\to p\equiv 1\mod 3\to \exists n: \ p \mid n^2+3$; instead, you can just consider $n = 3^{\frac{3k+1}{2}}a$. Otherwise, I have an alternative, complete solution: Suppose that there are only finitely many primes $p_i$ such that $p_i \mid n_i^2+3$ and $p_i \mid m_i^3-a$ for some integers $n_i$ and $m_i$. Consider the product $x$ of all these prime numbers, as well as $m = 3^2 a^3 x^4$, $n =3^2 a^2 x^3$, $k = (3^3 a^4 x^6-1)a$ and a prime number $p$ such that $p \mid 3^3 a^4 x^6+1$. We successively note that $p$ is prime to $3$ and to every prime number $p_i$. Moreover, $p \mid 3 (3^3 a^4 x^6+1) = n^2+3$ and $p \mid (n^2+3)k = 3 (3^3 a^4 x^6+1)(3^3 a^4 x^6-1)a = (3^6 a^8 x^12-1)$ $= 3 (3^6 a^9 x^12-a) = 3 (m^3-a)$, so that $p \mid m^3-a$. Since $p$ is not any of the numbers $p_i$ we first mentioned, we get a contradiction. QED.

All numbers of the form $3^{3k}a^2 + 1$ where $k$ varies are relatively prime, so it immediately follows infinitely many primes divide $3^{3k}a^2 + 1$ for some $k$

Rust wrote: Let $m=-3^ka$, and $p\mid 3^{3k}a^2+1$, then if $k$ is odd $\genfrac {(} {)} {} {} {-3}{p} = 1\to p\equiv 1\mod 3\to \exists n: \ p \mid n^2+3$. and here i thought my solution was overkill XD

want to know an over kill? let $p=12k-1$ so there is an $n$ such that $p| n^2+3$ and $p|i^3 -j^3$ if and only if $p|i-j$ so $0,1,8,27,...,(p-1)^3)$ is a complete residue $ BUDAM DISH$