#include <bits/stdc++.h>

using namespace std;
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");

void euclidex(int a, int b, long long &x, long long &y){
  if(b == 0){
    x = 1;
    y = 0;
    return;
  }
  euclidex(b, a % b, x, y);
  long long aux = y;
  y = x - 1LL * (a / b) * y;
  x = aux;
}

int main()
{
  int a, b;
  long long x, y;
  fi >> a >> b;
  euclidex(a, b, x, y);
  x = (x + b) % b;
  fo << x;
  fi.close();
  fo.close();
  return 0;
}