#include <fstream>
std::ifstream fin("inversmodular.in");
std::ofstream fout("inversmodular.out");
int cmmdc(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1, y = 0; return a;
    }
    else{
        int x1, y1, d;
        d = cmmdc(b, a % b, x1, y1);
        x = y1;
        y = x1 - (a / b) * y1;
        return d;
    }
}
int main(){
    int a, N;
    fin >> a >> N;
    int x, y;
    cmmdc(a, N, x, y);
    if(x <= 0){
        x += N + (x % N);
    }
    fout << x;
}