#include <stdio.h>

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

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