De ce contează?
Ai două rigle: una cu marcaje din 48 în 48 de milimetri, alta din 36 în 36. Vrei cea mai lungă unitate care „încape" exact în amândouă, fără rest. Începi cu cea mare, 48, dar nu intră fix în 36 — rămâne o bucată de 12. Acum întrebi același lucru, dar despre 36 și bucata de 12. Tot scurtezi întrebarea la rest, până când una intră fix în cealaltă. Ultima bucată rămasă e răspunsul. Asta face algoritmul lui Euclid.
Intuiția
Cel mai mare divizor comun (CMMDC) al lui a și b este cel mai mare număr care
le împarte pe amândouă fără rest. În loc să-l căutăm încercând divizori, ne
folosim de o observație: dacă un număr le împarte pe amândouă, atunci împarte și
restul împărțirii lor. Așa putem înlocui perechea (a, b) cu o pereche mai
mică (b, a % b) care are exact același CMMDC — și repetăm până restul devine 0.