#include <fstream>
#define ll long long
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int A, N;

void EuclidExtins(ll &x, ll &y, int a, int b){
    if (!b){
        x=1;
        y=0;
    }
        else {
            EuclidExtins(x, y, b, a%b);
            int aux = x;
            x = y;
            y = aux - y*(a / b);
    }
}
int main()
{
    in >> A >> N;

    ll x1 = 0, y1 = 0;

    EuclidExtins(x1, y1, A, N);

    if ( x1 <=0 ){
        x1 = N + x1%N;
    }

    out << x1;

    return 0;
}