Euklido algoritmas

Eukldo algortmas, 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 = bq₁ + r₁; q₁ – nepilnasis dalmuo, r₁ – liekana. Nuosekliai dalijant gaunamos lygybės:

a = bq₁ + r₁ (0 ≤ r₁ < b),

b = r₁q₂ + r₂ (0 ≤ r₂ < r₁),

r₁ = r₂q₃ + r₃ (0 ≤ r₃ < r₂),

......................................

r_n–2 = r_n–1q_n + r_n (0 ≤ r_n < r_n–1),

r_n–1 = r_nq_n+1 + r_n+1 (r_n+1 = 0);

čia visi q_i – teigiami sveikieji skaičiai ir 0 ≤ r_i < r_i–1 iki lygios nuliui liekanos r_n+1. Paskutinė nelygi nuliui liekana r_n 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.