#include <iostream>
#include <fstream>

std::pair<int, int> euclid(int a, int b) {
    int x = 1, y = 0;
    if (b == 0) {
        return std::make_pair(x, y);
    }

    std::pair<int, int> pair = euclid(b, a % b);

    return std::make_pair(pair.second, pair.first - (a / b) * pair.second);
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}


int main() {
    std::ifstream input("inversmodular.in");
    std::ofstream output("inversmodular.out");

    int a, n;
    input >> a >> n;
    int ans = euclid(a, n).first;
    while (ans < 0) ans += n;
    output << ans;
    return 0;
}