#include <cstdio>
#include <cstdint>
#include <utility>

std::pair<int64_t, int64_t> gcd(int64_t a, int64_t b){
    int32_t s[3]={1}, t[3]={0, 1};
    int64_t q, r;

    while (b){
        q = a/b;
        r = a%b;

        s[2] = s[0]-q*s[1];
        t[2] = t[0]-q*t[1];

        s[0]=s[1], t[0]=t[1], a=b;
        s[1]=s[2], t[1]=t[2], b=r;
    }

    return std::make_pair(s[0], t[0]);
}

int64_t pinv(int64_t a, int64_t b){
    int64_t sol = gcd(a, b).first;

    while (sol<0) sol += b;

    return sol;
}

int main()
{
    int a, b;

    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%d %d", &a, &b);
    printf("%lld", pinv(a, b));
    return 0;
}