#include <iostream>
#include <fstream>

#define ll long long

using namespace std;

int X, M;

void extendedGCD(ll &u, ll &v, int p, int q)  
{  
    if (!q)  
        u = 1, v = 0;  
    else  
    {             
        extendedGCD(u, v, q, p % q);
        ll temp = u;
        u = v;
        v = temp - v * (p / q);
    }
}

int main()
{
    long long inverse = 0, tempVar;
    
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");

    fin >> X >> M;
    extendedGCD(inverse, tempVar, X, M);

    if (inverse <= 0)
        inverse = M + inverse % M;

    fout << inverse << endl;

    return 0;
}