Click to reveal hidden text

First we show that either $40$ divides n or $49$ does. Tile the board with the number $a^ib^j$ in square $(i,j)$ where $a$ is a primitive $40$ root of unity and $b$ a primitive $49$ root of unity, the sum of the numbers on each square we put is $0$, so the total sum of the numbers in the big square must be $0$, so we get $40|n$ or $49|n$. Now from here it is easy to show since $(49,40)=1$ that $n=49x+40y$, iff $49|n$, then $n$ is at least $49+49.40=2009$ iff $40|n$ then $n$ is at least $49.40+40=2000$ and finally a $2000.2000$ can be tiled using both squares!