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

using namespace std;

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

int A, N;

void euclid(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1;
        y = 0;
        return;
    }
    int x1, y1;
    euclid(b, a % b, y1, x1);
    x = x1;
    y = y1 - (a / b) * x1;
}

void solve() {
    fin >> A >> N;
    int x, y;
    euclid(A, N, x, y);
    fout << (x % N + N) % N << '\n';
}

signed main() {
    solve();
    return 0;
}