#include <fstream>
 
using namespace std;

ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");
int x, y, d;
void euclide(int a, int b, int& x, int& y, int& d)
{
    if (b == 0)
    {
        a = d;
        x = 1;
        y = 0;
        return;
    }
    int x1, y1, q = a / b;
    euclide(b, a%b, x1, y1, d);
    x = y1;
    y = x1 - y1*q;
}
 
int main()
{
    int A, N, X;
    fi >> A >> N;
    euclide(A, N, x, y, d);
    if (x < 0)
    {
        while (x < 0)
            x += N;
    }
    fo << x;
    return 0;
}