#include <iostream>
#include <fstream>

using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

long long a , n;

pair <long long, long long> euclid(long long x, long long y){

    if(y == 0)
        return {1, 0};
    auto p = euclid(y, x % y);
    return {p.second, p.first - (x / y) * p.second};
}

int main() {

    ios::sync_with_stdio(false);

    in >> a >> n;

    pair<long long, long long> rez = euclid(a, n);

    long long afisare = rez.first;

    while(afisare < 0){
        afisare =+ n;
    }

    out << afisare;

    return 0;
}