#include <fstream>
#define LL long long
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
 
LL N,A,X,Y;
 
LL gcd(LL a, LL b, LL &x, LL &y){
 if(!b){
  x = 1;
  y = 0;
  return a;
 }
 LL  x0, y0, D;
 D = gcd(b, a % b, x0, y0);
 x = y0;
 y = x0-(a/b)*y0;
 return D;
}
 
LL inversmodular(LL A, LL N) {
   LL inv,ins;
   gcd(A, N, inv, ins);
   while(inv <= 0) inv += N;
   return inv;
}
 
int main()
{
  LL A, N;
  f >> A >> N;
  g << inversmodular(A, N) << '\n';   
  return 0;
}