#include <fstream>

using namespace std;

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

void egcd (int a, int b, long long &x, long long &y)
{
    if ( b == 0 )
    {
        x = 1;
        y = 0;
    }
    else
    {
        long long x0 = 0, y0 = 0;
        egcd (b, a%b, x0, y0);
        x = y0;
        y = x0 - (a/b) * y0;
    }
}

int main()
{
    long long invers, ins;
    int a, n;
    long long x = 0, y = 0;
    fin>>a>>n;
    egcd (a, n, x, y);
    while ( x <= 0 )
        x = n + x % n;
    fout<<x;
}