#include <cstdio>
#include <utility>
#define ll long long
using namespace std;

ll a, n;

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

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

    scanf("%lld %lld", &a, &n);

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

    ll k = rez.first;

    while(k<0)
        k+=n;
    printf("%lld", k);
    return 0;
}