#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

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

int euclid(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  
  int d = euclid(b, a % b, x, y);
  int xp = x, yp = y;
  x = yp;
  y = xp - (a / b) * yp;
  return d;
}

int main() {
  int a, n;
  fin >> a >> n;

  int x, y;
  euclid(a, n, x, y);

  x %= n;
  while (x < 0) x += n;

  fout << x;
  return 0;
}