#include <fstream>
std::ifstream fin("inversmodular.in");
std::ofstream fout("inversmodular.out");

long long int cmmdc(long long int a, long long int b, long long int &x, long long int &y){
    if(b == 0){
        x = 1, y = 0; return a;
    }
    else{
        long long int x1, y1, d;
        d = cmmdc(b, a % b, x1, y1);
        x = y1;
        y = x1 - (a / b) * y1;
        return d;
    }
}
int main(){
    long long int a, N;
    fin >> a >> N;
    long long int x = 0, y;
    cmmdc(a, N, x, y);
    if(x <= 0){
        x += N + (x % N);
    }
    fout << x;
}