#include <stdio.h>

void gcd(int A,int B,int &x,int &y)
{
if (B==0)
{
x=1;
y=0;
return;
}
int x0,y0;
gcd(B,A%B,x0,y0);
x = y0;
y = x0-(A/B)*y0;
return;
}

int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);

int A,B,x,y;

scanf("%d%d",&A,&B);
gcd(A,B,x,y);

while (x<0) x = (x + A)%B;

printf("%d",x%B);

}