On s'intéresse au problème suivant : étant donné un rectangle dont les dimensions sont des nombres entiers, quel est le nombre minimal de carrés de côté entier nécessaires pour le paver entièrement, sans déborder ?

Par exemple, pour le rectangle de dimensions 8×6, voici deux pavages possibles.