#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

pair<long long, long long> euclidExtins(long long a, long long b) {
    if (b == 0) {
        return make_pair(1, 0);
    }
    long long r = a % b;
    long long c = a / b;
    pair<long long, long long> p0 = euclidExtins(b, r);
    long long y = p0.first - c * p0.second;
    long long x = p0.second;
    return make_pair(x, y);
}

int main()
{
    long long A, N;
    fin >> A >> N;
    pair<long long, long long> p = euclidExtins(A, N);
    while (p.first < 0) {
        p.first += N;
    }
    fout << p.first << "\n";
    return 0;
}