#include <fstream>

using namespace std;

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

long long int InvMod (int a, int n);
void Euclid (int a, int b, long long int &x, long long int &y);

unsigned int A, N;

unsigned int i;

unsigned int X;

int main ()
{
    fin >> A >> N;
    X = InvMod(A,N);
    fout << X << '\n';
    return 0;
}

long long int InvMod (int a, int n)
{
    long long int inv, ins;
    Euclid(a,n,inv,ins);
    if (inv <= 0)
        inv = n + inv%n;
    return inv;
}

void Euclid (int a, int b, long long int &x, long long int &y)
{
    long long int xx, yy;
    if (b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    Euclid(b,a%b,xx,yy);
    x = yy;
    y = xx - yy*(a/b);
}