#include <bits/stdc++.h>
#define int long long
using namespace std;

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

void euclid (int a, int b, int &x, int &y){
  if (b == 0){
    x = 1;
    y = 0;
  }
  else{
    int x1, y1;
    euclid(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
  }
}

signed main(){
  int a, b; fin >> a >> b;
  int x, y;
  euclid(a, b, x, y);
  fout << (x + b) % b;
}