#include <stdio.h>

int a,n,inv,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,inv,aux);

	while (inv<=0)
		inv+=n;

	printf("%d\n",inv);

	return 0;
}