//nu farmez :P
#include <fstream>
#include <tuple>
#define mod 1000000007
#define int long long
using namespace std;


ofstream cout("inversmodular.out");
ifstream cin("inversmodular.in");
int euc(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}
signed main() {
  int n,a;
  cin >> a >> n;
  int temp,nimic;
  euc(a,n,temp,nimic);
  temp=(temp+100*n)%n;
  cout << temp <<'\n';
}