Алгоритм Евклида

function Evclid(x,y:integer):integer;
begin
repeat
if abs(x)>abs(y) then x:=x mod y
else y:=y mod x;
until (x=0) or (y=0);
Evclid:=abs(x+y);
end;
var n,p,m,i:integer;
begin
repeat
writeln('Введите 2 натуральны, взаимно простых числа');
readln(n,p);
until  Evclid(n,p)=1;
writeln('n=',n);
writeln('p=',p);
i:=1;
m:=0;
while (i<p)and(m=0) do
if i*n mod p=1 then m:=i
else inc(i);
if m=0 then write('Искомого числа нет')
else write('m=',m,' ',n,'*',m,'=',n*m,' mod ',p,'=1');
end.

{
Решение диофантового a*x+b*y=c уравнения в общем виде
 
Ограничение:
Коэффициенты a и b - только неотрицательные. Для отрицательных
нужно сделать ещё некоторые телодвижения, описанные в e-maxx.
}
program LinearDiophantineEquation;
 
  {Extended Euclidean algorithm}
  {
   на входе:
   a, b
   на выходе:
   НОД(a, b) = GCD(a, b)
   x, y - числа, такие, что a*x+b*y=GCD(a, b)
  }
  function ExtendedEuclideanAlgorithm(a, b: integer; var x, y: integer): integer;
  var
    x1, y1, d: integer;
  begin
    if (a = 0) then
    begin
      x := 0;
      y := 1;
      ExtendedEuclideanAlgorithm := b;
      Exit;
    end;
    d := ExtendedEuclideanAlgorithm(b mod a, a, x1, y1);
    x := y1 - (b div a) * x1;
    y := x1;
    ExtendedEuclideanAlgorithm := d;
  end;
 
var
  a, b, c: integer;
  Xg, Yg, g: integer;
  X0, Y0: integer;
  k: integer;
begin
  a := 10;
  b := 23;
  c := 1;
  {рассмотрим некоторые вырожденные случаи, доступные на данном этапе}
  {
   1. a=0, b=0, c=0 - бесконечное множество решений с произвольными x и y
   2. a=0, b=0, c<>0 - нет ни одного решения
   }
  if (a = 0) and (b = 0) then
  begin
    if (c = 0) then
      writeln('Бесконечное множество решений с любыми значениями x и y.')
    else
      writeln('Нет ни одного решения.');
    Exit;
  end;
  {нахождение НОД(a,b) и дополнительных переменных}
  g := ExtendedEuclideanAlgorithm(a, b, Xg, Yg);
  {на основе новых данных рассмотрим ещё один вырожденный случай
  3. c не делится на GCD(a, b) - нет ни одного решения
  }
  if (c mod g) <> 0 then
  begin
    writeln('Нет ни одного решения.');
    Exit;
  end;
  {нахождение одного решения}
  X0 := Xg * (c div g);
  Y0 := Yg * (c div g);
  {нахождение решения в общем виде}
  (*
  writeln('Решение диофантова уравнения ', a, 'x+', b, 'y=', c, ' в общем виде:');
  writeln('x=', X0, '+', (b div g), 'k');
  writeln('y=', Y0, '-', (a div g), 'k');
  *)
  {теперь подгонка к решению задачи на основе диофантового уравнения}
  k := (b - X0) div b;
  writeln('m=', X0 + b * k, '<', b);
end.

program task;
 
  {Extended Euclidean algorithm}
  {
   на входе:
   a, b
   на выходе:
   НОД(a, b) = GCD(a, b)
   x, y - числа, такие, что a*x+b*y=GCD(a, b)
  }
  function ExtendedEuclideanAlgorithm(a, b: integer; var x, y: integer): integer;
  var
    x1, y1, d: integer;
  begin
    if (a = 0) then
    begin
      x := 0;
      y := 1;
      ExtendedEuclideanAlgorithm := b;
      Exit;
    end;
    d := ExtendedEuclideanAlgorithm(b mod a, a, x1, y1);
    x := y1 - (b div a) * x1;
    y := x1;
    ExtendedEuclideanAlgorithm := d;
  end;
 
var
  Ng, Pg, g: integer;
  k: integer;
  m, n, p: integer;
begin
  n := 103;
  p := 23;
  {нахождение НОД(n,p) и дополнительных переменных}
  g := ExtendedEuclideanAlgorithm(n, p, Ng, Pg);
  {теперь подгонка к решению задачи на основе диофантового уравнения}
  k := (p - Ng) div p;
  if Ng + p * k >= p then
    Dec(k);
  m := Ng + p * k;
  writeln('m=', m, '<', p);
  writeln('m*n=', m * n, ' mod ', p, ' = ', (m * n) mod p);
end.