Задание №2

Даны натуральные числа х и у, не равные нулю одновременно. Найти d=НОД (х, у) и такие целые q и w, что d = q*x + w*y.

Решение:

Введем переменные p, q, r, s, m и n, такие, что m = p*a + q*b, n = r*a + s*b. Первоначально m = a = x, n = b = y.

Имеем программу:

Program example1;

Var

x, y: integer;

p, q, r, s, m, n: integer;

{Вспомогательные переменные}

d: integer;

{Значение наибольшего общего делителя}

begin

read (x, y);

m:=x; n:=y; p:=1; q:=0; r:=0; s:=1;

Repeat

If m>n

then

begin

k:=m div n;

m:= m mod n;

p:=p-k*r;

q:=q-k*s

end

else

begin

k:=n div m;

n:=n div m;

r:=r-k*p;

s:=s-k*q

end;

Until (m=0) or (n=0);

If m=0

then

begin

d:=n; q:=r; w:=s

end

else

begin

d:=m; q:=p; w:=q

end;

writeln (d, ‘ – ‘, q, ‘ * ‘, x, ‘ + ‘, w, ‘ * ‘, y);

readln

end.