#include<cstdio>
#include<algorithm>
using std::pair;
using std::make_pair;

pair<int,int> egcd (int a,int b)
{
	if(!b)
		return make_pair (1,0);
	int q=a/b;
	int r=a%b;
	pair<int,int> pr=egcd (b,r);
	int s=pr.first;
	int t=pr.second;
	return make_pair (t,s-q*t);
}

int main()
{
	freopen ("inversmodular.in","r",stdin);
	freopen ("inversmodular.out","w",stdout);
	int a,n;
	scanf ("%d%d",&a,&n);
	int r=egcd (a,n).first;
	while(r<0)
		r+=n;
	printf ("%d",r);
	return 0;
}