Нахождение НОД

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

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

Program Example_50;
Var x, y: Integer; {исходные данные}
p, q, r, s, m, n: Integer; {введенные вспомогательные переменные}
к: Integer; {для изменения значений P, q, r, s}
d: Integer; {значение наибольшего общего делителя}
Begin
Read(x, у);
m:=x; n:=y; р:=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 mod 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);
End.

Значения переменных p, q, r, s изменяются следующим образом:

• как только значение переменной m уменьшается на k*n, значение р уменьшается на k*r, а q уменьшается на k*S;
•  аналогично, как только значение n уменьшается на k*m, значения переменных r и s уменьшаются соответственно на k*p и на k*q.