#include <cstdio>

using namespace std;

void GCD (int A, int B, int &X, int &Y)
{
    if (B==0)
    {
        X=1;
        Y=0;
        return;
    }
    int X0, Y0;
    GCD (B, A%B, X0, Y0);
    X=Y0;
    Y=X0-Y0*(A/B);
}

int main()
{
    freopen ("inversmodular.in", "r", stdin);
    freopen ("inversmodular.out", "w", stdout);
    scanf ("%d %d", &A, &N);
    int X, Y;
    GCD (A, N, X, Y);
    if (X<0)
    {
        X=N+X%N;
    }
    printf ("%d\n", X);
    return 0;
}