#include <stdio.h>

int a,n,rez,aux;

void euclid(int a, int b, int &x, int &y)
{
	if (b==0){
		x=1; y=0;
	}
	else {
		int x0=0, y0=0;
		euclid(b,a % b, x0, y0);
		x=y0;
		y=x0-(a/b)*y0;
	}
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d %d",&a,&n);
	euclid(a,n,rez,aux);
	if (rez<=0)
		rez=n + rez % n;
	printf("%d\n",rez);
	fclose(stdin); fclose(stdout);
	return 0;
}