#include <cstdio>
FILE *f,*g;
long long aux,x,y;
int a,n;

void euclid(long long &x,long long &y,long long a,long long b) {

if (!b) {
	x = 1;
	y = 0;
	}
else {
	euclid(x,y,b,a%b);
	aux=x;
	x=y;
	y=aux-y*(a/b);
	}


}

int main() {
f=fopen("invermodular.in","r");
g=fopen("inversmodular.out","w");

fscanf(f,"%d%d",&a,&n);

euclid(x,y,a,n);

if (x<=0) {
	x=x % n + n;
	}

fprintf(g,"%lld",x);

return 0;
}