#include <fstream>
#define ll long long
using namespace std;
ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");
ll a,n;
void euclid (ll x,ll y,ll &a,ll &b)
{
    if (y == 0)
    {
        a = 1;
        b = 0;
        return;
    }
    ll a0,b0;
    euclid(y,x%y,a0,b0);
    a = b0;
    b = a0 - (x/y)*b0;
}
int main()
{
    ll x,y;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> n;
    euclid(a,n,x,y);
    while (x<0)
        x = x + n;
    cout << x << ' ';
    return 0;
}