#include <bits/stdc++.h>

using namespace std;

void extindedEuclid (long long x, long long y, long long &a, long long &b, long long &d) {
    if (y == 0) {
        d = x;
        a = 1;
        b = 0;
        return ;
    }
    extindedEuclid(y, x % y, a, b, d);
    long long newA = b;
    long long newB = a - b * (x / y);
    a = newA;
    b = newB;
}

int main()
{
    freopen ("inversmodular.in", "r", stdin);
    freopen ("inversmodular.out", "w", stdout);
    long long A, n;
    long long a, b, d;
    cin >> A >> n;
    extindedEuclid(A, n, a, b, d);
    a %= n;
    if (a < 0) {
        a += n;
    }
    cout << a;
    return 0;
}