#include <cstdio>
#define ll long long

int a, n;

void cmmdc(int a, int n, ll &x, ll &y)
{
	if (!n)
	{
		x=1;
		y=0;
	} else
	{
		cmmdc(n, a%n, x, y);
		ll aux=x;
		x=y;
		y=aux-y*(a/n);
	}
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d %d",&a,&n);
	ll x, y;
	cmmdc(a,n,x,y);
	printf("%d",(n+x%n)%n);
}