#include <cstdio>

using namespace std;

inline int gcd(int A, int B, int &X, int &Y)
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return A;
    }

    int D, X0, Y0;
    D = gcd(B, A % B, X0, Y0);
    // X0 * B + Y0 * (A - (A / B) * B)
    // X0 * B + Y0 * A - Y0 * B * (A / B)

    X = Y0;
    Y = X0 - Y0 * (A / B);
    return D;
}

int main()
{
    freopen("inversmodular.in", "rt", stdin);
    freopen("inversmodular.out", "wt", stdout);

    int N, P;
    scanf("%d %d", &N, &P);
    int D, X, Y;
    D = gcd(N, P, X, Y);

    // N * X + P * Y == 1
    // N * X == 1 (mod P)
    
    printf("%d\n", X);

    return 0;
}