Tiling puzzle: solution

My last post was a little tiling puzzle: you can read it here. In this post I want to quickly give the solution.

Represent a red tile by $1$ and a blue tile by $-1$; and think of the square in coordinate $(a,b)$ as the monomial $x^ay^b$. Then the question is equivalent to asking when the polynomial $p_{N,M}(x,y)=\sum_{a=1}^N\sum_{b=1}^Mx^ay^b$ is in the ideal generated by $(1-x+x^2, 1-y+y^2)$. These are cyclotomic polynomials for sixth roots of unity, so one can test whether $p_{N,M}(x,y)$ is in this ideal by evaluating it at $(\zeta, \zeta)$, where $\zeta$ is a primitive sixth root of unity. Now it’s an exercise to check that $p_{N,M}(\zeta, \zeta)=0$ if and only if one of $N,M$ is divisible by 6!