#include <stdio.h>

void ee(int a, int b, long long *x, long long *y)
{
    if (b == 0)
	{
        *x = 1;
        *y = 0;
		return;
    }
    long long x0, y0;
    ee(b, a % b, &x0, &y0);
	*x = y0;
    *y = x0 - (a / b) * y0;
}


int main()
{
	long long x=0,k=0;
	int a,n;
	
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	
	scanf("%d%d",&a,&n);
	
	ee(a,n,&x,&k);
	
	if (x<=0)
		x=n+x%n;
	
	printf("%lld\n",x);
	
	fclose(stdin);
	fclose(stdout);	
	return 0;
}