#include <fstream>

using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

typedef long long ll;

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

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

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

    Euclid(a,b,x,y);

    return x;
}

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

    X = inv_modular(A,N);
    while(X < 0)
        X += N;
    out<<X;

    return 0;
}