#include <iostream>

using namespace std;

typedef long long ll;

ll n, a;

pair<ll, ll> euclidExtins(ll X, ll Y) {
    if(!Y) return {1, 0};
    pair<ll, ll> p = euclidExtins(Y, X % Y);
    return {p.second, p.first - p.second * (X / Y)};
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%lld%lld", &a, &n);
    ll ans = euclidExtins(a, n).first;
    while(ans < 0) ans += n;
    printf("%lld", ans);
    return 0;
}