#include <iostream>
#include <fstream>
using namespace std;

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


long long A, N;

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

    long long x0, y0;
    GCD(b, a % b, x0, y0);

    x = y0;
    y = x0 - (a / b) * y0;
}

int main() {
    fin >> A >> N;

    long long x, y;
    GCD(A, N, x, y);

    long long inv = x % N;

    if (inv < 0) {
        inv += N;
    }

    fout << inv << '\n';
}