Soit m le nombre de carreaux traversés cherché.

On se ramène si possible à un rectangle plus petit de longueur n' et de largeur p', avec : n = n' pgcd (n;p) et p = p' pgcd (n;p). Si m' est le nombre de carreaux traversés dans ce nouveau rectangle, on a alors : m = m' pgcd (n;p).

Maintenant, on doit chercher m' en fonction de n' et p'. La diagonale ne passe par aucun coin, et traverse n' - 1 lignes verticales et p' - 1 lignes horizontales. Chaque ligne ( horizontale ou verticale ) traversée correspond à un carreau traversé, sachant qu' à ce compte, on oublie un coin. Alors m' = ( n' - 1 ) + ( p' - 1 ) + 1 = n' + p' - 1.

Finalement, m = ( n' + p' - 1 ) pgcd (n;p) = n + p - pgcd (n;p)

Le nombre de carreaux traversés par la diagonale d'un rectangle de longueur n et de largeur p est n + p - pgcd ( n ; p ).