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 bi, ostataka dijeljenja prema jednadžbama: a = nb + b1; b = n1b1 + b2; b1 = n2b2 + b3; …; dok ostatak bk ne bude jednak nuli. Posljednji ostatak bi, 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.

Euklidov algoritam. Hrvatska enciklopedija, mrežno izdanje. Leksikografski zavod Miroslav Krleža, 2018. Pristupljeno 8.12.2019. <http://www.enciklopedija.hr/Natuknica.aspx?ID=18595>.