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

int a,n;
void citire(){
 f>>a>>n;
}

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

int invers_modular(int a,int m){
 int x,y,d;
 euclid_extins(a,m,x,y,d);
 while(x<0)x+=m;
 return x;
}
int main(){
 citire();
 g<<invers_modular(a,n);
}