#include <iostream>
#include <fstream>

using namespace std;

long long extEuclid(long long a, long long b, long long *x, long long *y)
{
    long long x0 = 1, x1 = 0, y0 = 0, y1 = 1;

    while(1){
        int q = a / b;
        int r = a % b;
        if(!r){
            return b;
        }
        a = b;
        b = r;
        *x = x0 - q*x1;
        *y = y0 - q*y1;
        x0 = x1;
        x1 = *x;
        y0 = y1;
        y1 = *y;
    }
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    long long a, n, x, y;
    scanf("%lld%lld", &a, &n);

    extEuclid(a, n, &x, &y);

    printf("%ld\n", x % n);

    return 0;
}