#include <cstdio>

using namespace std;

void euclid(int a, int b, int &x, int &y)
{
	if (b==0)
	{
		x=1;
		y=0;
		return;
	}
	int x1,y1,q=a/b;
	euclid(b,a%b,x1,y1);
	x=y1;
	y=x1-q*y1;
}



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