De ce contează?
Ai 48 de bomboane roșii și 18 bomboane albastre și vrei să le împarți în pungi identice, fără să rămână nimic pe afară: fiecare pungă cu același număr de roșii și același număr de albastre. Care e cea mai mare pungă posibilă? Răspunsul e exact cel mai mare număr care încape fix și în 48, și în 18 — adică cel mai mare divizor comun al lor.
Intuiția
Cel mai mare divizor comun (CMMDC) a două numere este cel mai mare număr care le împarte pe amândouă fără rest. Pentru 48 și 18 răspunsul este 6: 48 = 6·8 și 18 = 6·3. Ideea genială a lui Euclid e că nu trebuie să cauți acest 6 încercând toți candidații — poți să-l afli înlocuind, pas cu pas, numărul mai mare cu restul împărțirii. Numerele scad repede, dar divizorul comun rămâne neatins.