#include <fstream>

using namespace std;
ifstream in ("inversmodular.in");
ofstream out ("inversmodular.out");

long long int gcd(long long int a, long long int b, long long int &x, long long int &y) {
 if (a == 0) {
  x = 0;
  y = 1;
  return b;
 }

 long long int x1, y1, d;
 d = gcd(b % a, a, x1, y1);

 x = y1 - (b / a) * x1;
 y = x1;

 return d;
}

int main()
{
    long long int x, y, a, n, invmod;

    in>> a >> n ;

    invmod = gcd(a, n, x, y);

    while(x < 0)
        x += n;
    out<< x ;
    return 0;
}