#include <fstream>

using namespace std;

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

int a,n;
long long inv=0,ins=0;

void invm(long long &x,long long &y, int a,int b) {
    if (b==0) {
        x=1;y=0;
    }
    else {
        invm(x,y,b,a%b);
        long long z;
        z=x;
        x=y;
        y=z-(a/b)*y;
    }
}
int main () {
    f >> a >> n;
    invm(inv,ins,a,n);
    if (inv<=0) inv=n+inv%n;
    g << inv << '\n';
    f.close();g.close();
    return 0;
}