#include<cstdio>
using namespace std;
#define ll_ long long
void inv(ll_ &x, ll_ &y, ll_ a, ll_ b){
	if(!b)
		x=1,y=0;
	else{
		inv(x,y,b,a%b);
		ll_ aux=x;
		x=y;
		y=aux-y*(a/b);
	}
}
int main(){
	ll_ x=0,y,a,n;
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&a,&n);
	inv(x,y,a,n);
	if(x<=0) x=n+x%n;
	printf("%lld\n",x);
	return 0;
}