#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;

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

int ext_gcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1; y = 0;
    return a;
  }
  int x1, y1;
  int d = ext_gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - a/b * y1;

  return d;
}

int main(void) {
  // freopen("inversmodular.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int a, n;
  fin >> a >> n;
  int x, y;
  ext_gcd(n, a, x, y);

  y %= n; if (y < 0) { y += n; }
  fout << y << endl;


  return 0;
}