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

Теория 
Нека  и  са естествени числа и редицата

е определена така, че всяко  е остатък от делението на пред-предния член на предния член, т.е.

Тогава  – най-големият общ делител на  и , е равен на
 – последния ненулев член на редицата.

Верността на алгоритъма следва от съжденията:
 Нека , тогава 
  за всяко ненулево

Запис с думи 
Взимайки двете дадени на входа на алгоритъма числа 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 се пресмята по следния начин:

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

Алгоритми
Теория на числата