#include<stdio.h>

int N,A,X,aux;

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

inline void pregateste()
{FILE *pin=fopen("inversmodular.in","r");
fscanf(pin,"%d",&A);
fscanf(pin,"%d",&N);
fclose(pin);}

inline void rezolva()
{
int y;
cmmdc(A,N,X,y);
if(X<=0)
  X+=N;
}

inline void incheie()
{
FILE *pout=fopen("inversmodular.out","w");
fprintf(pout,"%d",X);
fclose(pout);
}

int main()
{
pregateste();
rezolva();
incheie();
return 0;
}