#include<stdio.h>
#define ll long long
ll A,N,inv,aux;

void euclid ( ll a, ll b, ll &x, ll &y)
{
	ll x0,y0;
	
	if(!b) { x=1; y=0; return ;}
	
    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("%lld %lld",&A,&N);
	
	euclid(A,N,inv,aux);
	
	if(inv>0) inv%=N;
	else if(inv<0) inv=N+inv%N;
	
	printf("%lld",inv);
	
	return 0;
}