Algoritmul lui Euclid

Algoritmul lui Euclid este un procedeu prin care este determinat cel mai mare divizor comun a două numere întregi a, b (respectiv a două polinoame cu coeficienţi într-un corp): Conform teoremei împărţirii cu rest, există $q_1 \!$ şi $r_1 \!$ astfel ca:

$a = bq_1+r_1 \!$ şi $0 \le r_1 < b. \!$

(respectiv $r_1=0 \!$ sau $grad \; r_1 < grad \; b). \!$

Mai departe, există $q_2 \!$ şi $r_2 \!$ cu:

$b = r_1q_2+r_2 \!$ şi $0 \le r_2 < r_1. \!$

(respectiv $r_2=0 \!$ sau $grad \; r_2 < grad \; r_1). \!$

La fel, există $q_3 \!$ şi $r_3 \!$ cu:

$r_1 = r_2q_3+r_3 \!$ şi $0 \le r_3 < r_2. \!$

(respectiv $r_3=0 \!$ sau $grad \; r_3 < grad \; r_2). \!$

şi aşa mai departe.

Primul element diferit de zero din șirul (finit) $b, r_1, r_2, r_3, \cdots \!$ este cel mai mare divizor comun al elementelor a, b.