/*
	Keep It Simple!
*/

#include<stdio.h>
long long n,m;
void euclid(long long a,long long b, long long *d,long long *x, long long *y)
{
	if(!b)
	{
		*d=a;
		*x=1;
		*y=0;
	}
	else
	{
        long long x0,y0;
		euclid(b,a%b,d,&x0,&y0);
		*x = y0;
		*y = x0 - ( a/b ) * y0;
	}
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	long long d,x,y;
	euclid(n,m,&d,&x,&y);
	if ( x <= 0 )
		x = m + x%m;
	printf("%lld",x);
}