#include<stdio.h>
#include<algorithm>
using namespace std;
int gcdex(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int d,y0,x0;
	d=gcdex(b,a%b,x0,y0);
	x=y0;
	y=x0-(a/b)*y0;
	return d;
}
int main()
{
	int A,N,Y,X,d;
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&A,&N);
	
	d=gcdex(A,N,X,Y);
	d=X%N;
	if(d>=0)
		printf("%d\n",d);
	else
		printf("%d\n",d+N);
	return 0;
}