#include<cstdio>
int a,n,x,y,z;

void E(int a,int b,int *x,int *y)
{int p,r;  
if(!b)
      (*x)=1,(*y)=0;
else
      E(b,a%b,&p,&r),(*x)=r,(*y)=p-(a/b)*r;}

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