I. megoldás. A feladat ,,csak akkor'' részét bizonyítjuk, a másik irány úgyis nyilvánvaló. Tegyük fel indirekt módon, hogy $k$ sem az $n$-et, sem az $m$-et nem osztja, és az $n\times m$-es táblát mégis le tudtuk fedni $k\times 1$-es dominókkal. Legyen $n=ak+b$ és $m=ck+d$, ahol $a\mathrm{,}b\mathrm{,}c\mathrm{,}d$ egészek és $0<b\mathrm{,}d<k$. Számozzuk be a tábla mezőit az első $k$ darab természetes számmal oly módon, hogy az $i\mathrm{.}$ sor $j\mathrm{.}$ mezőjére $\left(i+j-2\right)$-nek $k$-val vett osztási maradékát írjuk. (1. ábra). Világos, hogy a fedésben részt vevő dominók midegyike $k$ darab különböző számot fed le, függetlenül attól, hogy vízszintes vagy függőleges helyzetben van. Ezért a táblán miden szám ugyanannyiszor fordul elő. A táblából vágjunk le jobbról egy $\left(ak\right)\times m$ nagyságú részt, ekkor minden szám előfordulását ugyanannyival csökkentettük, hiszen a levágott rész lefedhető $k\times 1$-es dominókkal. Mivel a maradék $b\times m$-es táblán ugyanannyiszor szerepel minden szám, azért ha ebből alulról még egy $b\times \left(ck\right)$-as részt is levágunk, akkor a fennmaradó $b\times d$ nagyságú táblán is ugyanannyiszor szerepelnek a számok 0-tól $\left(k-1\right)$-ig. Megmutatjuk, hogy ez nem igaz. Az általánosságnak nem megy rovására, ha felteszzük, hogy $0<d\le b<k$. Ekkor a $b-1$ szám minden sorban szerepel, tehát pontosan $d$ darab van belőle a táblán, a második sorban azonban nem szerepel a 0, tehát 0-ból legfeljebb $d-1$ darab lehet a táblán (2. ábra). Ellentmondásra jutottunk, ami a feladatbeli állítást igazolja.
II. megoldás. Az előző megoldás ötletét komplex számokkal ötvözve még gyorsabban célhoz érhetünk. Legyen ugyanis $\epsilon =\text{cos}\left(2\pi /k\right)+i\text{sin}\left(2\pi /k\right)$ az első $k$-adik egységgyök, és tegyük fel, hogy az $n\times m$-es táblát lefedtük $k\times 1$-es dominókkal. Ha a tábla mezőit oly módon töltjük ki komplex számokkal, hogy az $r\mathrm{.}$ sor $s\mathrm{.}$ mezőjére az ${\epsilon }^{r+s-2}$ egységgyököt írjuk, akkor minden $k\times 1$-es dominó a $k\mathrm{.}$ egységgyökök egy teljes rendszerét fedi le, amelyeknek 0 az összegük. Így a táblán lévő összes egységgyökök is 0-t adnak összegül, azaz