#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int A, N, x, y;
int euclid(int a, int b, int &x, int &y) {
    if(!b) {
        x = 1;
        y = 0;
        return a;
    }
    int x0, y0, d;
    d = euclid(b, a%b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
    return d;
}
int main()
{
    fin>>A>>N;
    euclid(A, N, x, y);
    while(x < 0) {
        x = x + N;
    }
    fout<<x;
    fin.close();
    fout.close();
    return 0;
}