#include<fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a,n,b,x,y,d;

void euclid_ex(int a,int b,int &d,int &x,int &y){
  if(b==0){
    d=a;
    x=1;y=0;
    }else{
     int x0,y0;
     euclid_ex(b,a%b,d,x0,y0);
     x=y0;
     y=x0-(a/b)*y0;
    }
}

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

  euclid_ex(a,n,d,x,y);
  x%=n;
  while(x<0) x+=n;

  g<<x;

 return 0;
}