/*
	Keep It Simple!
*/

#include<stdio.h>
long long n,m;
void euclid(int a,int b, int *d,int *x, int *y)
{
	if(!b)
	{
		*d=a;
		*x=1;
		*y=0;
	}
	else
	{
		int 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("%d%d",&n,&m);
	long long d,x,y;
	euclid(n,m,&d,&x,&y);
	if ( x <= 0 )
		x = m + x%m;
	printf("%lld",x);
}