#include <iostream>
#include <fstream>

using namespace std;

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

typedef long long ll;

ll cmmdc(ll a, ll b, ll &x, ll &y) {
  if(b == 0) {
    x = 1;
    y = 0;
    return a;
  }else {
    ll ans = cmmdc(b, a % b, x, y);
    ll xPrim = x, yPrim = y;
    x = yPrim;
    y = (xPrim - (a / b) * yPrim);
    return ans;
  }
}

int main() {

  ll a, n, x, y, ans = 0;
  in >> a >> n;
  ans = cmmdc(a, n, x, y);
  if(x > 0) {
    out << x % n << '\n';
  }else {
    out << x + ((-x) / n + 1) * n << '\n';
  }
  return 0;
}