Estonia — Open Contests

Numbers $n$ and $n^3$ give the same remainder when dividing by $6$. Also, $m^2 + m + 1$ is odd and gives the remainder $0$ or $1$ when dividing by $3$. The only possibility to get $0$ as the remainder is when $m = 3k+1$, but then
$$n^3 = (9k^2 + 6k + 1) + (3k + 1) + 1 = 9k^2 + 9k + 3 = 3(3k^2 + 3k + 1)$$
which leads to a contradiction, since if $n^3$ is divisible by $3$, it is also divisible by $3^3$, but $3k^2 + 3k + 1$ is not divisible by $3$. Hence the remainder of $n^3$ is $1$ both when dividing by $2$ or $3$, consequently its remainder when dividing by $6$ is $1$.

The remainder $1$ is possible: take $n = 1$ and $m = 0$ (or $n = 7$ and $m = 18$).