#include <fstream>

using namespace std;

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

int main()
{
    ifstream cin ("inversmodular.in");
    ofstream cout ("inversmodular.out");

    int a, n, x1, y1;

    cin >> a >> n;

    euclid(a, n, x1, y1, n);

    if (x1 < 0)
        x1 += n;

    cout << x1 << '\n';
    return 0;
}