#include<stdio.h>

void eu( int x,int y,int &a,int &b,int &d)
{
	if(y==0)
	{
		a=1;
		b=0;
		d=x;
		return;
	}
	int a1,b1;
	eu(y,x%y,a1,b1,d);
	a=b1;
	b=a1-b1*(x/y);// ( x/y ) e parte intreaga din x/y
}
int a,n;
int main()
{
	int x=0,y=0,z=0;
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&a,&n);
	eu(a,n,x,y,z);
	if(x>=n)
		printf("%d",x%n);
	else if( x>=0 )
		printf("%d",x);
	else
	{
		while(x<0)
			x+=n;
		printf("%d",x);
	}
	return 0;
}