//#include <iostream>
#include <fstream>

using namespace std;

ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");


long long gcd_ext(long long A, long long N, long long* X, long long* Y) {
    if (A == 0) {
        *X = 0;
        *Y = 1;
        return N;
    }

    long long X1, Y1;
    long long gcd = gcd_ext(N % A, A, &X1, &Y1);

    *X = Y1 - (N / A) * X1;
    *Y = X1;

    return gcd;
}

long long mod_inv(long long A, long long N) {
    long long X, Y;
    long long gcd = gcd_ext(A, N, &X, &Y);

    if (gcd != 1) {
        return -1;
    }

    
    while (X < 0) {
        X += N;
    }

    return X;
}

int main(){
    long long A, N;
    cin >> A >> N;
    cout << mod_inv(A, N);
    return 0;
}