#include<stdio.h>
long a,n,d,x,y;

void euclid2(long a,long b,long *d,long *x,long *y)
{long x0,y0;   
if(b==0) 
      {(*d)=a;
      (*x)=1;
      (*y)=0;} 
else 
      {euclid2(b,a%b,d,&x0,&y0);
      (*x)=y0;
      (*y)=x0-(a/b)*y0;}}

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