Ser vi på figurene til Hanne, gjør hun det samme hver gang: hun legger et størst mulig kvadrat inntil rektangelet, og det som blir igjen er et nytt, mindre rektangel. Dette gjentas helt til det som er igjen selv er et kvadrat (helt dekket av like store kvadrater).

Dette er nøyaktig framgangsmåten i Euklids algoritme for å finne den største felles faktoren (gcd) til to hele tall — her sidelengdene $a$ og $b$ i rektangelet.

Algoritmen kan beskrives slik, i ord:

1. La $a$ være den lengste siden og $b$ den korteste siden i rektangelet.
2. Legg på et størst mulig kvadrat med sidekant $b$ inntil rektangelet.
3. Det som er igjen av rektangelet, har sidene $b$ og $r$, der $r$ er resten når $a$ deles på $b$ (altså $r=amodb$).
4. Sett $a=b$ og $b=r$, og gjenta fra steg 2.
5. Når resten $r$ blir $0$, er hele det opprinnelige rektangelet dekket av kvadrater med sidekant lik den siste verdien av $b$. Dette er den maksimale sidekanten kvadratene kan ha.

Som pseudokode:

SETT a = lengste side
SETT b = korteste side
SÅ LENGE b ≠ 0
    r = a MOD b
    a = b
    b = r
SLUTT SÅ LENGE
Sidekanten til de største kvadratene er a

Vi bruker samme algoritme til å skrive et program. Programmet spør etter sidene i rektangelet og regner ut den maksimale sidekanten med Euklids algoritme (modulo-operasjonen % i Python):

def storste_kvadrat(a, b):
    while b != 0:
        a, b = b, a % b
    return a

lengde = 18
bredde = 8
sidekant = storste_kvadrat(lengde, bredde)
print(f"Kvadratene kan maksimalt ha sidekant {sidekant}.")

Kjøring av programmet med et rektangel på $18\times 8$ gir følgende utskrift:

Kvadratene kan maksimalt ha sidekant 2.

Det stemmer: $18=2\cdot 9$ og $8=2\cdot 4$, så $2$ er den største felles faktoren til $18$ og $8$, og dermed den maksimale sidekanten kvadratene kan ha for å dekke rektangelet helt.

Programmet gir altså sidekanten til de største kvadratene som kan dekke et rektangel, ved å bruke Euklids algoritme (gjentatt modulo-operasjon) helt til resten blir $0$.