#include<cstdio>
using namespace std;
int x,y,a,n,d;
void cmmdc(int a, int b, int &d, int &x, int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		d=a;
	}
	else
	{
		int x0,y0;
		cmmdc(b,a%b,d,x0,y0);
		x=y0;
		y=x0-(a/b)*y0;
	}
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d %d\n",&a,&n);
	cmmdc(a,n,d,x,y);
	while(x<=0) x=x+n;
	printf("%d\n",x);
	fclose(stdin);
	fclose(stdout);
	return 0;
}