#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, n;
  long long x, y;
  fi >> a >> n;
  euclidex(a, n, x, y);
  x = (x + n) % n;
  fo << x;
  return 0;
}