Портал:Математика/Изабрани чланак јул
У математици, Еуклидов алгоритам је ефикасан начин за одређивање највећег заједничког делиоца (НЗД) датих бројева. Алгоритам носи име по старогрчком математичару Еуклиду, који га је навео у VII и X књизи својих Елемената.
НЗД два броја је највећи број који истовремено дели оба без остатка. Еуклидов алгоритам је заснован на принципу да се највећи заједнички делилац два броја не мења уколико се мањи број одузме од већег, па се затим одреди НЗД новодобијеног броја и мањег од претходна два.
На пример, 21 је НЗД за 252 и 105 (252 = 21 × 12; 105 = 21 × 5); пошто је 252 − 105 = 147, НЗД за 147 и 105 је такође 21. Како је већи од два полазна броја на овај начин смањен, понављањем поступка добијаће се све мањи бројеви, док се један од њих не сведе на нулу. У том тренутку, други број је једнак највећем заједничком делиоцу два полазна броја.
Уколико се обрне редослед корака у Еуклидовом алгоритму, НЗД се може изразити као збир два полазна броја од којих је сваки помножен неким целим бројем, у претходном примеру је 21 = 5 × 105 + (−2) × 252. Ова важна особина је позната као Безуов идентитет.