#include <iostream>
#include <fstream>
using namespace std;
long long n,a;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int main()
{   in>>a>>n;
long long y0=0,y1=1,r,c,y,aux;
aux=n;
while(a!=0)
{  r=n%a;
   c=n/a;
   n=a;
   a=r;
   y=y0-c*y1;
   y0=y1;
   y1=y;
}
while(y0<0) y=y+aux;
out<<y0;
    return 0;
}