#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int a, n;
int x, y;

void ee(int a, int n, int &x, int &y) {
 if(!n) {
  x=1;
  y=0;
  return;
 }
 int xp, yp;
 ee(n, a%n, xp, yp);
 x=yp;
 y=xp-(a/n)*yp;
}

int main() {
 f>>a>>n;

 ee(a, n, x, y);

 while(x<0)
  x+=n;

 g<<x;

 f.close();
 g.close();
 return 0;
}