Eukldo algortmas, metodas, kuriuo randamas 2 sveikųjų skaičių (arba daugianarių) didžiausias bendrasis daliklis arba 2 atkarpų bendrasis matas. Jei a ir b yra sveikieji skaičiai ir a ≥ b, tai dalijant a iš b su liekana visada a = bq1 + r1; q1 – nepilnasis dalmuo, r1 – liekana. Nuosekliai dalijant gaunamos lygybės:
a = bq1 + r1 (0 ≤ r1 < b),
b = r1q2 + r2 (0 ≤ r2 < r1),
r1 = r2q3 + r3 (0 ≤ r3 < r2),
......................................
rn–2 = rn–1qn + rn (0 ≤ rn < rn–1),
rn–1 = rnqn+1 + rn+1 (rn+1 = 0);
čia visi qi – teigiami sveikieji skaičiai ir 0 ≤ ri < ri–1 iki lygios nuliui liekanos rn+1. Paskutinė nelygi nuliui liekana rn yra skaičių a ir b didžiausias bendrasis daliklis. Pagal Euklido algoritmą randamas didžiausias bendrasis daliklis ir įrodoma, kad didžiausias bendrasis daliklis egzistuoja. Analogiškai randamas daugianarių didžiausias bendrasis daliklis ir atkarpų bendrasis matas. Euklido algoritmas išdėstytas Euklido Pradmenyse.
Citata
Nors buvo dedamos visos pastangos laikytis citavimo stiliaus taisyklių, gali pasitaikyti tam tikrų neatitikimų. Jei turite klausimų, prašome vadovautis atitinkamu stiliaus vadovu arba kitais šaltiniais.