Euklidov algoritam

Euklidov algoritam (po Euklidu koji ga je opisao u sedmoj knjizi Elemenata), postupak kojim se određuje najveća zajednička mjera dvaju cijelih brojeva, dvaju polinoma ili dviju dužina. Npr. za brojeve a i b, uz uvjet a ≥ b, lančanim dijeljenjem nastaje niz brojeva b_i, ostataka dijeljenja prema jednadžbama: a = nb + b₁; b = n₁b₁ + b₂; b₁ = n₂b₂ + b₃; …; dok ostatak b_k ne bude jednak nuli. Posljednji ostatak b_i, različit od nule, najveća je zajednička mjera (M). Tako za brojeve 70 i 42 vrijedi: 70 = 1 · 42 + 28; 42 = 1 · 28 + 14; 28 = 2 · 14 + 0; slijedi M = 14.