#include <fstream>

// A * X mod N = 1

std::ifstream  cin("inversmodular.in");
std::ofstream cout("inversmodular.out");

long int A, N, nr, a, b, c;

long int euclid(long int x0, long int x1, long int& alpha0, long int& beta1) {

  if (x1 == 0) {
    alpha0 = 1;
    beta1 = 0;
    //cout << "check x0 = " << x0 << " x1 = " << x1 << "alpha = " << alpha0 << " beta1 = " << beta1 << std::endl;
    return x0;
  }

  long int c1, x2, cmmdc;
  c1 = x0 / x1;
  x2 =  x0 % x1;
  long int alpha1, beta2;
  
  cmmdc = euclid(x1, x2, alpha1, beta2);

  alpha0 = beta2;
  beta1 =  alpha1 - beta2 * c1;
  //cout << "check x0 = " << x0 << " x1 = " << x1 << "alpha0 = " << alpha0 << " beta1 = " << beta1 << std::endl;
  return cmmdc;
}

int main () {

  cin >> A >> N;
  //cout << "check A = " << A << std::endl;
  //cout << "check N = " << N << std::endl;
  long int x, y, cmmdc;

  cmmdc = euclid(N, A, x, y);  
  cout << (y % N + N ) % N;   
  return 0;

}