#include <stdio.h>

void gcd(int A,int B,long long &x,long long &y)
{
if (B==0)
{
x=1;
y=0;
return;
}
long long 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;
long long x,y;

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

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

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

}