Алгоритм Евклида для нахождения наибольшего общего делителя (НОД).

Алгоритм Евклида — алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин.

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную по отношению теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

Описание

Пусть a и b целые числа, не равные одновременно нулю, и последовательность чисел a, b, r₁ > r₂ > r₃ > ... >rn определена тем, что каждое r_k — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

a = bq₀ + r₁
b = r₁q₁ + r₂
r₁ = r₂q₂ + r₃
...
r_k−2 = r_k−1q_k−1 + r_k
...
r_n−1 = r_nq_n

Тогда НОД(a,b), наибольший общий делитель a и b, равен r_n, последнему ненулевому члену этой последовательности.

Релизация Pascal

  function nod( a, b: longint): longint; 
  begin
   while (a <> 0) and (b <> 0) do begin
     if a >= b then 
       a:= a mod b 
     else 
       b:= b mod a;
   end;
   nod:= a + b;
  end;

Релизация Pascal в рекурсивном виде

  function nod(var a, b: longint): longint; 
  begin
   if (a = 0) or (b = 0) then
     if a = 0 then
       nod:= b
     else 
       nod:= a
   else 
     if a >= b then 
       nod:= nod( a mod b, b)
     else 
       nod:= nod( a, b mod a)
  end;