//Rares 0net
using namespace std;
using ULL=unsigned long long int;
#ifdef RS
#include<d:\Rares0.hpp>
#else
#include<fstream>
const string N_file="inversmodular";
ifstream fin(N_file+".in");
ofstream fout(N_file+".out");
#define cin fin
#define cout fout
#endif
#define endl '\n'
#define INF 0x3f3f3f3f
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
void EuclidExtins(int a, int b, int &d, int &x, int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        d=a;
        return;
    }
    int x1, y1;
    EuclidExtins(b, a%b, d, x1, y1);
    x=y1;
    y=x1-(a/b)*y1;
}
int InversModular(int A, int N)
{
    int d, x, y;
    EuclidExtins(A, N, d, x, y);
    for(; x<0; x+=N);
    return x;
}
ULL N, M;
void Solve()
{
    cin>>N>>M;
    cout<<InversModular(N, M);
}
main()
{
    Solve();
}