#include <fstream>
#define ll long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
/**
    (A,N)=1;
    A*X=1%N, X - inversul modular al lui A
    A*X+N*Y=1;
*/
pair<ll,ll> euclid_ext(ll a,ll n)
{
    if(n==0)
    return {1,0};
    auto p=euclid_ext(n,a%n);
    return{p.second,p.first-(a/n)*p.second};
}


int main()
{
    ll a,n,x,y;
    fin>>a>>n;
    auto p1=euclid_ext(a,n);
    if(p1.first<0)
    {
        while(p1.first<0)
            p1.first+=n;
    }
    fout<<p1.first;//<<" "<<p1.second;



    return 0;
}