#include <fstream>
#define in "inversmodular.in"
#define out "inversmodular.out"

using namespace std;

ifstream fin(in);
ofstream fout(out);

typedef long long ll;

inline void Euclid(int a,int b,ll &x,ll &y,const int &mod)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
    }
    else
    {
        ll x0,y0;
        Euclid(b,a%b,x0,y0,mod);

        x = y0 % mod;
        y = x0 - a/b*y0 % mod;
    }
}

int inv_modular(int a,int mod)
{
    int b = mod;
    ll x,y;

    Euclid(a,b,x,y,mod);

    return x;
}

int main()
{
    int A,N,X;
    fin>>A>>N;

    X = inv_modular(A,N);
    while(X<0)
    {
        X+=N;
    }
    fout<<X;

    return 0;
}