#include <fstream>

using namespace std;
  
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

void get_xy(long long a, long long b, long long &x, long long &y) {

  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }

  long long x0, y0;
  get_xy(b, a % b, x0, y0);
  x = y0; 
  y = x0 - (a / b) * y0;
}

int main(int argc, char const *argv[]) {
  
  long long a, n;
  cin >> a >> n;

  long long x, y;
  get_xy(a, n, x, y);
  while (x < 0) {
    x += n;
  }

  cout << x << '\n';
}