#include<stdio.h> 
int n;
long long x,y;
void euler(int a,int b)
{
	long long aux;
	if(b==0)
	{
		x=1;
		y=0;
	}
	else
	{
		euler(b,a%b);
		aux=x;
		x=y;
		y=aux-(a/b)*y;
	}
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	int a;
	scanf("%d%d",&a,&n);
	euler(a,n);
	while(x<0)
	x=n+x%n;
	printf("%lld",x);
	return 0;
}