#include <fstream>

using namespace std;

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

int a,n,x,y;

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

}


int main(){
    fin>>a>>n;
    euclid(a,n,x,y);
    while(x<0) x+=n;
    fout<<x;


    return 0;
}