#include <fstream>

using namespace std;

int A,N,X,Y;

int inv(int a,int b,int &x,int &y){

    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int xa,ya;
    int d = inv(b,a%b,xa,ya);
    x=ya;
    y=xa+a/b*ya;
    return d;
}

int main(){

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

    fin >> A >> N;

    inv(A,N,X,Y);

    while(X<=0)
        X+=N;

    fout << X << "\n";

}