#include<stdio.h>

int n,a;

void euclid(int a, int b, int &x, int &y) {
	if(b==0) {
		x=1;
		y=0;
		return;
	}
	int q=a/b,xx,yy;
	euclid(b,a%b,xx,yy);
	x=yy;
	y=xx-q*yy;
}

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