program extended_euclid_algorithm;
var
x,b,a,m,tempx,y,tempy,c,d,q,r,inverse:integer;
begin
	tempx:=1; 
	tempy:=0;
	c:=0; d:=1;
	readln(a,m);
	b:=m;
	if(m<0) then
	begin
		m:=-m;
		a:=-a;
	end;
	while(m<>0) do
	begin 
		x:=tempx; y:=tempy;
		tempx:=c; tempy:=d;
		q:= a div m;
		q:=-q;
		c:=q*c;
		d:=q*d;
		c:=c+x;
		d:=d+y;
		r:=a mod m;
		a:=m;
		m:=r;
	end;
	writeln('the values of x and y are',tempx,' ',tempy);
	writeln('the gcd is given by ',a);
	if(a = -1) then
	begin
		a:=-a;
	end;
	if(a<>1) then
	writeln('the modular inverese cannot be find')
	else
	begin
	if(tempx<0) then
	inverse:= (b+tempx) mod b
	else
	inverse:=tempx mod b;
	writeln('the inverse is given by ',inverse);
	end;
end.