#include <stdio.h>

void euclid(long long *x,long long *y,int a,int b)
{
  if(b==0)
    {
      *x=1;
      *y=0;
    }
  else
    {
      euclid(x,y,b,a%b);
      long long aux=*x;
      *x=*y;
      *y=aux-(*y)*(a/b);
    }
  
}


int main(void)
{
  long long x,y;
  int a,n;
  FILE *f1=fopen("inversmodular.in","r"),*f2=fopen("inversmodular.out","w");
  if(f1==NULL || f2==NULL)
    {
      perror(NULL);
      return 1;
    }
  fscanf(f1,"%d %d",&a,&n);
  euclid(&x,&y,a,n);
  fprintf(f2,"%lld",x);
  fclose(f1);
  fclose(f2);
  return 0;
}