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

with Text_IO;
use Text_IO;

procedure Euklides_rozsz is

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

begin

   -- set all data
   nwd_a := 153;
   nwd_b := 1326;

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

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

   -- initialize r and nwd
   q := 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) loop
      a := b;
      b := r;

      x := x2 - q*x1;
      x2 := x1;
      x1 := x;

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

      nwd := r;
      q := a/b;
      r := a - q*b;

   end loop;

   -- present results
   Put_Line("NWD(" & Integer'Image(nwd_a) & ", " & Integer'Image(nwd_b) & ") = " & 
             Integer'Image(nwd) & " = " & Integer'Image(x) & " * " & Integer'Image(nwd_a) & " + " &
             Integer'Image(y) & " * " & Integer'Image(nwd_b));

   if nwd = 1 then
      Put_Line(Integer'Image(nwd_b) & " * " & Integer'Image(y) & " mod " &
               Integer'Image(nwd_a) & " = 1");
   end if;
   
end;