cmmdc

Algoritmul, pas cu pas

Ideea de pornire: cmmdc-ul a două numere

Totul se sprijină pe cmmdc-ul a două numere, calculat cu algoritmul lui Euclid: cât timp $b \ne 0$, înlocuim perechea $(a, b)$ cu $(b, a \bmod b)$; când $b$ ajunge $0$, valoarea rămasă în $a$ este cmmdc-ul. cmmdc-ul mai multor numere se obține aplicând Euclid pe rând, ca o acumulare: $g \leftarrow \text{cmmdc}(g, a_i)$.