Proof for a $n \times m$ checkerboard tiling

Question

I believe it is a basic problem, but I would like some help proving this statement:

Prove that a $n\times m$ checkerboard can be filled with $k\times 1$ tiles if and only if k divides m or n.

Answer 1

Hint: The statement said "checkerboard". Can we color the squares in a useful way? Say, a way that makes each $k\times 1$ tile have one square of each color in it?

Answer 2

Here is an elegant approach which uses the complex numbers. Denote cell in $i$-th column and in $j$-th row as $(i,j)$. Also, define $\varepsilon$ as $e^{\frac{2\pi i}{k}}=\cos\frac{2\pi}{k}+i\sin\frac{2\pi}{k}$. Note that $\varepsilon^s=1$ iff $k|s$.

Then, write in each cell $(i,j)$ number $\varepsilon^{i+j}$. Firstly, in every $1\times k$ sum of numbers I the cells equals zero. Hence, sum of all numbers in the $n\times m$ also equals zero. On the other hand, sum of all number equals $(\varepsilon+\varepsilon^2+\ldots+\varepsilon^{n})(\varepsilon+\varepsilon^2+\ldots+\varepsilon^{m})$, which equal to $\varepsilon^2\cdot\frac{(\varepsilon^n-1)(\varepsilon^m-1)}{(\varepsilon-1)^2}$. Therefore, either $\varepsilon^n-1$, either $\varepsilon^m-1$ equals zero. As was mentioned before, it's mean that $k$ divides $m$ or $n$, as desired.