Algoritmul lui Euclid

De la Wikipedia, enciclopedia liberă

Algoritmul lui Euclid este un algoritm care calculează cel mai mare divizor comun (c.m.m.d.c.) al două numere întregi. El este bazat pe teorema împărţirii cu rest.

Fie a şi b două numere întregi, nu amândouă nule. Atunci algoritmul funcţionează in felul următor:

Pas 1)Daca b = 0, atunci c.m.m.d.c.(a,b) =  | a | . STOP.
Pas 2)Daca  atunci aplică Teorema Împărţirii cu Rest perechii (a,b). Se obţine astfel restul r.
Pas 3)Se întoarce la Pas 1) cu perechea (b,r). 

Proprietatea ZWOP din Axiomele lui Z, ne garantează că acest algoritm se termină într-un număr finit de pasi.