Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее положительное целое число, на которое делятся эти два числа. При этом, по определению, НОД(0,0)=0 и НОД(а,0)=|а|.

    В приведенной ниже программе НОД(a,b) вычисляется по алгоритму Евклида. С этой целью последовательно находятся остатки r_i от деления

 

и так пока r_n+1 не превратится в ноль. Тогда

 

     НОД нескольких чисел можно найти, используя соотношение

 

     Программа вычисления НОД

 

{NOD.pas

Сайт Algorithm (http://www.algorithm1.narod.ru/)

Автор проекта: Galina}

 

var a1,b1,f:integer;

function nod(a, b:integer):integer;

var r, r_1, r_2:integer;

begin

  r:=a; r_1:=b;

  while r_1 <> 0 do

  begin

    r_2:=r mod r_1;

    r:=r_1;

    r_1:=r_2;

  end;

  nod:=abs(r);

end;

 

begin

  writeln('Введите a1');

  readln(a1);

  writeln('Введите b1');

  readln(b1);

  f:=nod(a1,b1);

  writeln('NOD a1 и b1 = ',f);

end.