program Euklides_rozsz_d;
{$APPTYPE CONSOLE}
uses
  SysUtils;

//
// Rozszerzony algorytm Euklidesa
//
// www.algortym.org
// (c)2006 Tomasz Lubinski
//

var
   r, a, q, b : Integer;
   x, x1, x2 : Integer;
   y, y1, y2 : Integer;
   nwd_a, nwd_b, nwd : Integer;

begin
   //get all data
   writeln('Podaj pierwsza liczbe');
   readln(nwd_a);

   writeln('Podaj druga liczbe');
   readln(nwd_b);

   // a must be greater than b
   if (nwd_b > nwd_a) then
   begin
      nwd := nwd_b;
      nwd_b := nwd_a;
      nwd_a := nwd;
   end;

   
   //initialize a and b
   a := nwd_a;
   b := nwd_b;

   //initialize r and nwd
   q := Trunc(a/b);
   r := a - q*b;
   nwd := b;
   
   //initialize x and y
   x2 := 1;
   x1 := 0;
   y2 := 0;
   y1 := 1;
   x := 1;
   y := y2 - (q-1)*y1;
   
   while (r <> 0) do
   begin
      a := b;
      b := r;
      
      x := x2 - q*x1;
      x2 := x1;
      x1 := x;

      y := y2 - q*y1;
      y2 := y1;
      y1 := y;      

      nwd := r;
      q := Trunc(a/b);
      r := a - q*b; 
   end;

   
   //present results
   writeln('NWD(' + IntToStr(nwd_a) + ', ' + IntToStr(nwd_b) + ') = ' + IntToStr(nwd) + ' = ' + IntToStr(x) +
           ' * ' + IntToStr(nwd_a) + ' + ' + IntToStr(y) + ' * ' + IntToStr(nwd_b));

   if (nwd = 1) then
     writeln(IntToStr(nwd_b) + ' * ' + IntToStr(y) + ' mod ' + IntToStr(nwd_a) + ' = 1');

   readln;
   
end.