#include <bits/stdc++.h>
using namespace std;
typedef long long llong;

auto euclidExtins(int a, int b) {
  struct Euclid { int d, x, y; };
  if (b == 0) return Euclid {a, 1, 0};
  auto [d, x, y] = euclidExtins(b, a % b);
  return Euclid {d, y, x - (a / b) * y};
}

int pow(int n, int k, int m) {
  llong r = 1, c = n;
  while (k) {
    if (k & 1) r = r * c % m;
    c = c * c % m;
    k >>= 1;
  }
  return r;
}

void solve() {
  int a, n;
  cin >> a >> n;
  auto [d, x, y] = euclidExtins(a, n);
  cout << x + ((abs(min(0, x)) + n - 1) / n * n) << endl;
}

int main() {

  #ifdef LOCAL
  freopen("file.in", "r", stdin);
  #else
  freopen("inversmodular.in", "r", stdin);
  freopen("inversmodular.out", "w", stdout);
  #endif

  ios_base::sync_with_stdio(false), cin.tie(NULL);

  solve();
}