#include <fstream>

using namespace std;

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

void euclid(int a, int b,int & x,int & y)
{
    if(b == 0)
    {
        x = 1, y = 1;
    }
    else
    {
        int x1, y1;
        euclid(b, a % b, x1, y1);
        x = y1;
        y = x1 - a / b * y1;
    }
}

int P,N,X,Y;

int main()
{
    f>>N>>P;
    euclid(N, P, X,Y);
    while(X < 0)
        X += N;
    g << Y; // 5
    return 0;
}