Даны два натуральных числа a и b, не равные нулю одновременно. Вычислить НОД (a,b) - наибольший общий делитель а и b.

Решение (1 вариант).

  if a > b then begin
  | k := a;
  end else begin
  | k := b;
  end;
  {k = max (a,b)}
  {инвариант: никакое число, большее k, не является об-
  щим делителем}
  while not (((a mod k)=0) and ((b mod k)=0)) do begin
  | k := k - 1;
  end;
  {k - общий делитель, большие - нет}

(2 вариант - алгоритм Евклида). Будем считать , что НОД (0,0) = 0. Тогда НОД (a,b) = НОД (a-b,b) = НОД (a,b-a); НОД (a,0) = НОД (0,a) = a для всех a,b>=0.

  m := a; n := b;
  {инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
  while not ((m=0) or (n=0)) do begin
  | if m >= n then begin
  | | m := m - n;
  | end else begin
  | | n := n - m;
  | end;
  end;
  if m = 0 then begin
  | k := n;
  end else begin
  | k := m;
  end;

---