За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел.

Алгоритъмът на Евклид е алгоритъм за намиране на най-големия общ делител (НОД) на две естествени числа. Той е един от първите публикувани алгоритми. Описан е в книгата на Евклид „Елементи“ около 300 г. пр.н.е.

Нека ${\displaystyle a}$ и ${\displaystyle b}$ са естествени числа и редицата

${\displaystyle a,\,b,\,r_{1}>r_{2}>r_{3}>r_{4}>\cdots >r_{n}}$

е определена така, че всяко ${\displaystyle r_{k}}$ е остатък от делението на пред-предния член на предния член, т.е.

${\displaystyle a=bq_{0}+r_{1}}$

${\displaystyle b=r_{1}q_{1}+r_{2}}$

${\displaystyle r_{1}=r_{2}q_{2}+r_{3}}$

${\displaystyle \cdots }$

${\displaystyle r_{n-1}=r_{n}q_{n}}$

Тогава ${\displaystyle (a,b)}$ – най-големият общ делител на ${\displaystyle a}$ и ${\displaystyle b}$, е равен на ${\displaystyle r_{n}}$ – последния ненулев член на редицата.

Верността на алгоритъма следва от съжденията:

• Нека ${\displaystyle a=bq+r}$, тогава ${\displaystyle (a,b)=(b,r).}$
• ${\displaystyle (0,r)=r}$ за всяко ненулево ${\displaystyle r.}$

Взимайки двете дадени на входа на алгоритъма числа a и b, провери дали b е равно на 0.

Ако да, числото a е търсеният най-голям общ делител.

Ако не, повтори процеса, като използваш за входни данни b и остатъка, получен при деленето a на b (означаван по-долу с a mod b)

function gcd(a, b)
  if b = 0
     return a
  else
     return gcd(b, a mod b);

// := е оператор за присвояване на стойност
function gcd(a, b)
  while b ≠ 0
    var t := b
    b := a mod b
    a := t
  return a

Във всяка стъпка по-голямото число се заменя с остатъка му от деление на другото число (ако в първата стъпка има 8 и 6, то във втората ще има 2 и 6). Това се повтаря докато едно от двете числа не стане 0. Тогава отговорът е другото число (ако се продължи от предния пример, на третата стъпка числата ще са 2 и 0, от което се разбира, че НОД на 8 и 6 е 2).

Този алгоритъм е по-ефективен от споменатата по-долу негова вариация.

function gcd(a, b)
  while a ≠ b
    if a > b
      a := a – b
    else
      b := b – a
  return a

Най-големият общ делител на числата 1071 и 1029 се пресмята по следния начин:

${\displaystyle 1071=1\cdot 1029+42}$

${\displaystyle 1029=24\cdot 42+21}$

${\displaystyle 42=2\cdot 21+0}$

Следователно търсеният делител е 21.