const a=12345;  b=678900;
type num=int64;
var  d,x,y: num;
procedure gcd(a,b: num; var a1,x1,y1: num);
             var q,a2,x2,y2,a3,x3,y3: num;
                                 BEGIN
if (a=0) then         begin
  a2:=b;  x2:=0;  y2:=1 end else
if (b=0) then         begin
  a2:=a;  x2:=1;  y2:=0 end else begin
  a1:=a;  x1:=1;  y1:=0;
  a2:=b;  x2:=0;  y2:=1;
  repeat q:=a1 div a2;  x3:=x1-q*x2;
        a3:=a1 mod a2;  y3:=y1-q*y2;
        a1:=a2;  x1:=x2;  y1:=y2;
        a2:=a3;  x2:=x3;  y2:=y3
  until a3=0                   end END;
                                 BEGIN
gcd(a,b,d,x,y);
write('GCD(',a,', ',b,') = ',d,' = ',x,'*',a);
if y>=0 then write('+');
writeln(y,'*',b)                   END.