#include<cstdio>
using namespace std;
struct sol
{
	int x,y;
}p;

int A,N;

void read(),solve(),cmmdc(int,int,sol &p);

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&A,&N);
}

void solve()
{
	cmmdc(A,N,p);
	while(p.x<0)p.x+=N;
	printf("%d\n",p.x);
}

void cmmdc(int x,int y,sol &p)
{
	if(!y)
	{
		p.x=1;p.y=0;
		return ;
	}
	sol q;
	cmmdc(y,x%y,q);
	p.x=q.y;p.y=q.x-(x/y)*q.y;
}