#include <fstream>
using LL = long long;
LL A, N, modular_inverse;
 
 
LL ext_euclid(LL a, LL b)
{
    a %= b;
    if (a < 0)
    {
        a += b;
    }
 
    LL old_r = a, r = b;
    LL old_s = 1, s = 0;
    LL old_t = 0, t = 1;
    LL q, new_r, new_s, new_t;
    while (r != 0)
    {
        q = old_r / r;
        new_s = old_s - s * q;
        new_t = old_t - t * q;
        new_r = old_r % r;
        old_r = r, r = new_r;
        old_s = s, s = new_s;
        old_t = t, t = new_t;
    }
    return old_s;
}
 
 
int main()
{
    std::ifstream fisierIN("inversmodular.in");

    fisierIN >> A >> N;

    modular_inverse = ext_euclid(A, N);

    std::ofstream fisierOUT("inversmodular.out");
    fisierOUT << modular_inverse;
}