#include<fstream>
using namespace std;
ifstream f("inversmodular.in"); ofstream g("inversmodular.out");
#define ll long long
int A, N;
void gcd(ll &x, ll &y, int a, int b)
{   if (!b){ x = 1; y = 0; }
    else
    {   gcd(x, y, b, a % b);
        ll aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}
int main()
{   ll invers=0,ins;
    f>>A>>N;
    gcd(invers,ins,A,N);
    if (invers <= 0) invers = N + invers % N;
    g<<invers;
}