#include <fstream>

using namespace std;

pair<int, int> extended_euclid(int a, int b) {
  pair<int, int> result;
  if (a == 1){
    result.first = 1;
    result.second = 0;
  } else if (b == 1) {
    result.first = 0;
    result.second = -1;
  } else {
    int d = a / b, c = a % b;
    pair<int, int> p = extended_euclid(b, c);
    result.first = - p.second;
    result.second = - (p.second * d + p.first);
  }
  return result;
}

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int main() {
  int A, N;
  f >> A >> N;
  int result = extended_euclid(A, N).first;
  if (result < 0)
    result += N;
  g << result << std::endl;
  f.close();
  g.close();
  return 0;
}