Selection tests for the Balkan Mathematical Olympiad 2013

Because $589=19\times 31$, we will find all positive integers $n<589$ such that both $19$ and $31$ divide $n^2+n+1$. Let $n$ be such an integer. We have $$0\equiv n^2+n+1\equiv n^2+20n+1\equiv (n+10{)}^2-2^2\equiv (n+8)(n+12)(\mathrm{mod}19).$$ Hence, $19$ divides $n^2+n+1$ if and only if $n\equiv 7$ or $11(\mathrm{mod}19)$. On the other hand, we have $$0\equiv n^2+n+1\equiv n^2+32n+1\equiv (n+16{)}^2-10^2\equiv (n+26)(n+6)(\mathrm{mod}31).$$ Hence, $31$ divides $n^2+n+1$ if and only if $n\equiv 5$ or $25(\mathrm{mod}31)$. Using the fact that $8\times 31\equiv 1(\mathrm{mod}19)$ and $18\times 19\equiv 1(\mathrm{mod}31)$, we consider the following four cases:

1. If $n\equiv 7(\mathrm{mod}19)$ and $n\equiv 5(\mathrm{mod}31)$. There exists an integer $k$ such that $$n=7\times 8\times 31+5\times 18\times 19+k\times 19\times 31=501+589(k+5).$$ But $0<n<589$. We deduce that $n=501$.

2. If $n\equiv 7(\mathrm{mod}19)$ and $n\equiv 25(\mathrm{mod}31)$. There exists an integer $k$ such that $$n=7\times 8\times 31+25\times 18\times 19+k\times 19\times 31=273+589(k+17).$$ But $0<n<589$. We deduce that $n=273$.

3. If $n\equiv 11(\mathrm{mod}19)$ and $n\equiv 5(\mathrm{mod}31)$. There exists an integer $k$ such that $$n=11\times 8\times 31+5\times 18\times 19+k\times 19\times 31=315+589(k+7).$$ But $0<n<589$. We deduce that $n=315$.

4. If $n\equiv 11(\mathrm{mod}19)$ and $n\equiv 25(\mathrm{mod}31)$. There exists an integer $k$ such that $$n=11\times 8\times 31+25\times 18\times 19+k\times 19\times 31=87+589(k+19).$$ But $0<n<589$. We deduce that $n=87$.

Therefore, the possible values for $n$ are $87$, $273$, $315$, and $501$.