#include <iostream>
#include <fstream>

using namespace std;

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

int a, n;

void gcd(long &x, long &y, long a, long b) {
//  cout << x << " " << y << " " << a << " " << b << endl;
  if (!b)
    x = 1, y = 0;
  else {
    gcd(x, y, b, a % b);
    long aux = x;
    x = y;
    y = aux - y * (a / b);
//    cout << x << " " << y << " " << a << " " << b << endl;
  }
}

int main() {
  long invers = 0, y = 0;

  in >> a >> n;
  gcd(invers, y, a, n);

  if (invers <= 0)
    invers = n + invers % n;

  out << invers << endl;
  return 0;
}