#include <cstdio>

using namespace std;

long long x,y;
int a,b,c,n,i;
void inversm(int a, int b, long long &x, long long &y)
{
       long long k;
	if (b==0)
	{
       x=1;
       y=0;
	}
	else
	{
	inversm(b,a%b,x,y);
	k=x;
	x=y;
	y=k-(a/b)*y;
	}
}

int main()
{

	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d\n",&a,&n);
	inversm(a,n,x,y);

	while (x<0)
	x=n+x%n;

	printf("%d\n",x);
	fclose(stdin);
	fclose(stdout);
	return 0;
}