#include <cstdio>

using namespace std;

int a,n,x, y;

void euclid( int a, int b, int &x, int &y );

int main() 
{
 freopen("inversmodular.in", "r", stdin );
 freopen("inversmodular.out", "w", stdout );

 scanf("%d %d",&a,&n );

 euclid(n,a,x,y);

 while (y<0)
  y+=n;

 printf("%d\n", y);

return 0;
}

void euclid( int a, int b, int &x, int &y )
{
 if(b==0) 
 {
  x=1;
  y=0;
  return;
 }

 int x0,y0;
 int c=a/b;

 euclid(b,a%b,x0,y0);

 x=y0;
 y=x0-c*y0;
}