#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;
long long a,n;
pair <long long, long long> euclid(long long la, long long lb)
{
    if(lb==0)
    return {1,0};
    auto p=euclid(lb,la%lb);
    return {p.second,p.first-p.second*(la/lb)};
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld %lld", &a, &n);
    auto r=euclid(a,n);
    while(r.first<0)
        r.first+=n;
    cout<<r.first;
    return 0;
}