#include <bits/stdc++.h>
#define LL long long

using namespace std;

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

void gcd(LL& x, LL& y, LL a, LL b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }

    gcd(x, y, b, a % b);
    LL aux = x;
    x = y;
    y = aux - (a / b) * y;
}

int main() {
    LL x, n, ins, inv;
    fin >> x >> n;
    gcd(ins, inv, x, n);
    while (ins < 0)
        ins += n;
    fout << ins;
    return 0;
}