#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int A, N;
pair<int, int> euclidExtins(int a, int b) {
    if (b == 0) {
        return make_pair(1, 0);
    }
    else {
        pair<int, int> p0 = euclidExtins(b, a % b);
        pair<int, int> p;
        p.first = p0.second;
        p.second = p0.first - (a / b) * p0.second;
        return p;
    }
}
int main()
{
    fin >> A >> N;
    pair<int, int> ans = euclidExtins(A, N);
    if (ans.first <= 0) {
        ans.first = N + (ans.first % N);
    }
    fout << ans.first << "\n";
    return 0;
}