#include <fstream>

using namespace std;

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

long long a, n, x, y;

inline void euclidpp (long long a, long long b, long long &x, long long &y){
    long long xa, ya, d;
    if (b == 0){
        y = 0, x = 1;
    }
    else{
        euclidpp (b, a%b, xa, ya), x = ya, y = xa - (a/b)*ya;
    }
}

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