#include <iostream>
#include <fstream>

using namespace std;
#define LL long long int
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");
LL x, y, d;
void euclide(LL a, LL b, LL& x, LL& y, LL& d)
{
    if (b == 0)
    {
        a = d;
        x = 1;
        y = 0;
        return;
    }
    LL x1, y1, q = a / b;
    euclide(b, a%b, x1, y1, d);
    x = y1;
    y = x1 - y1*q;
}

int main()
{
    LL A, N, X;
    fi >> A >> N;
    euclide(A, N, x, y, d);
    if (x < 0)
    {
        while (x < 0)
            x += N;
    }
    fo << x;
    return 0;
}