#include <stdlib.h>
#include <stdio.h>
void cmmdc(long long a,long long b,long long &x,long long &y)
{int aux;
 if(b==0)
 {x=1;
  y=0;
 }
 else
 {cmmdc(b,a%b,x,y);
  aux=x;
  x=y;
  y=aux-y*(a/b);
 }
}

int main ()
{freopen("inversmodular.in","r",stdin);
 freopen("inversmodular.out","w",stdout);
 long long a,n,x,y;
 scanf("%lld %lld",&a,&n);
 cmmdc(a,n,x,y);
 if(x<0)x+=n;
 printf("%lld",x);
 return 0;
}