Algoritmul lui Euclid

De la Wikipedia, enciclopedia liberă

Acest articol are nevoie de adăugarea unor legături interlinguale. Dacă asemenea legături nu sunt disponibile, puteţi ajuta prin înlocuirea acestui format cu unul mai explicit.

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.