Šablon:IČ – Euklidov algoritam
brojeve 252 i 105
U matematici, Euklidov algoritam je efikasan način za određivanje najvećeg zajedničkog delioca (NZD) datih brojeva. Algoritam nosi ime po starogrčkom matematičaru Euklidu, koji ga je naveo u VII i X knjizi svojih Elemenata.
NZD dva broja je najveći broj koji istovremeno deli oba bez ostatka. Euklidov algoritam je zasnovan na principu da se najveći zajednički delilac dva broja ne menja ukoliko se manji broj oduzme od većeg, pa se zatim odredi NZD novodobijenog broja i manjeg od prethodna dva. Na primer, 21 je NZD za 252 i 105 (252 = 21 × 12; 105 = 21 × 5); pošto je 252 − 105 = 147, NZD za 147 i 105 je takođe 21. Kako je veći od dva polazna broja na ovaj način smanjen, ponavljanjem postupka dobijaće se sve manji brojevi, dok se jedan od njih ne svede na nulu. U tom trenutku, drugi broj je jednak najvećem zajedničkom deliocu dva polazna broja. Ukoliko se obrne redosled koraka u Euklidovom algoritmu, NZD se može izraziti kao zbir dva polazna broja od kojih je svaki pomnožen nekim celim brojem, u prethodnom primeru je 21 = 5 × 105 + (−2) × 252. Ova važna osobina je poznata kao Bezuov identitet. (Čitav članak...)