FANDOM


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.