#include <stdio.h>

long long int euclidExtended(long long int a, long long int b, long long int *x, long long int *y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }

    long long int x1, y1;
    long long int gcd = euclidExtended(b % a, a, &x1, &y1);

    *x = y1 - (b / a) * x1;
    *y = x1;

    return gcd;
}

long long int modInverse(long long int A, long long int N) {
    long long int x, y;
    long long int gcd = euclidExtended(A, N, &x, &y);

    if (gcd != 1) {
        // Modular inverse doesn't exist
        return -1;
    }

    // Ensure the result is positive
    long long int result = (x % N + N) % N;
    return result;
}

int main() {
    long long int A, N;

    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%lld %lld", &A, &N);

    long long int inverse = modInverse(A, N);

    printf("%lld", inverse);

    return 0;
}