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$).