#include<stdio.h>


long long euclid(long long a,long long n,long long *x,long long *y)
{
  if(n==0)
    {
      *x=1;
      *y=0;
      return a;
    }

  long long x1,y1;

  long long d=euclid(n,a%n,&x1,&y1);

  *x=y1;
  *y=x1-(a/n)*y1;

  return d;
}

int main()
{
  FILE *fin=fopen("inversmodular.in","r");
  FILE *fout=fopen("inversmodular.out","w");

  if(fin==NULL || fout==NULL)
    {
       perror("Eroare la deschiderea fisierelor");
       return 1;
    }

  long long a,n,x,y;

  if(fscanf(fin,"%lld %lld",&a,&n)!=2)
    {
      printf("citire incorecta\n");
      return 1;
    }

  euclid(a,n,&x,&y);

  x=x%n;

  if(x<0)
    x=x+n;

  fprintf(fout,"%lld\n",x);
  
  fclose(fin);
  fclose(fout);
  return 0;
}