#include <algorithm>

using namespace std;

#define ll long long

ll a,n;
void euclid(ll &x,ll &y,ll a,ll n)
{
	if(n==0)
	{
		x=1,y=0;
		return ;
	}
	
	euclid(x,y,n,a%n);
	
	ll aux=x;
	x=y;
	y=aux-a/n*y;
}

ll solve(ll a,ll n)
{
	ll x,y;
	x=0;
	euclid(x,y,a,n);
	
	return (n+x)%n;
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	
	scanf("%lld %lld",&a,&n);
	
	printf("%lld\n",solve(a,n));
	return 0;
}