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

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);
z=x;
if(z>=1&&z<n)
      printf("%ld\n",z);
else
      if(z<1)
              {while(z<1)
                   z+=n;
              printf("%ld\n",z);}
      else
              {while(z>n)
                   z-=n;
              printf("%ld\n",z);}
fclose(stdin);
fclose(stdout);
return 0;}