#include <fstream>

using namespace std;

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

void euclidExtins(int a, int b, int& x, int& y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return ;
    }
    int q = a/b;
    int nx, ny;
    euclidExtins(b, a-q*b, nx, ny);
    x = ny;
    y = nx-q*ny;
}


int main()
{
    int a, n, x, y;
    in >> a >> n;
    euclidExtins(a, n, x, y);
    while(x < 0)
    {
        x += n;
    }
    while(x > n)
    {
        x -= n;
    }
    out << x;
    return 0;
}