#include <iostream>
#include <fstream>

using namespace std;

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()
{
    long long a, n;
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%lld %lld", &a, &n);
    long long k=euclid(a, n).first;
    while(k<0)
        k+=n;
    cout<<k;

    return 0;
}