L'algorithme d'Euclide en rectangles

Découper dans un rectangle de côtés entiers les plus grands carrés possibles, puis recommencer dans ce qui reste : le côté du dernier carré est le PGCD des deux côtés, et les nombres de carrés sont les quotients de l'algorithme d'Euclide.

On choisit deux entiers $a$ et $b$ entre $1$ et $120$. Dans le rectangle de côtés $a$ et $b$, la page enlève autant de carrés que possible de côté égal au petit côté, puis recommence dans le rectangle restant ; elle écrit en regard les divisions euclidiennes successives. Pour $45$ et $12$ : $45 = 12 \times 3 + 9$, $12 = 9 \times 1 + 3$, $9 = 3 \times 3 + 0$, soit trois carrés de côté $12$, un de côté $9$ et trois de côté $3$.

Ce que cela signifie : si $a = bq + r$, les couples $(a\,;b)$ et $(b\,;r)$ ont les mêmes diviseurs communs, donc le même PGCD ; les restes décroissent strictement, l'un d'eux est nul, et le PGCD est le dernier reste non nul, ici $3$. Le dernier carré est le plus grand carré qui pave tout le rectangle. Avec $89$ et $55$, deux termes consécutifs de la suite de Fibonacci, chaque étape sauf la dernière n'enlève qu'un carré et il faut neuf divisions ; avec $120$ et $7$, deux suffisent. Les quotients successifs forment la fraction continue de $\dfrac ab$.

Le piège le plus courant est de s'arrêter un cran trop tard et de répondre $0$ : le PGCD est le dernier reste non nul, c'est-à-dire le diviseur de la division qui tombe juste.