We have $589=pq$ with $p=19$ and $q=31$. Now, $p\mid n^2+n+1\implies p\mid (2n+1)^2+3$. Thus $(2n+1)^2\equiv 16\pmod{p}$. This yields $2n+1\equiv \pm 4\pmod{19}$, that is $2n\in\{-5,3\}\iff n\in \{7,11\}\pmod{19}$. Likewise, $q\mid (2n+1)^2+3$ implies $(2n+1)^2\equiv 11^2\pmod{q}$, yielding $2n+1\equiv \pm 11\pmod{31}$. Thus, $n\in\{-6,5\}\pmod{19}$. The rest is easy.