# include <cstdio>
using namespace std;
long long a, n, x, y;
/*
    Oricare ar fi A,N intregi, exista doua numere X, Y intregi astfel incat
    A * X + N * Y = cmmdc(A, N)
*/
void invers_modular(long long a, long long b, long long &x, long long &y)
{
    if(!b)
    {
        x = 1; y = 0;
    }
    else
    {
        long long x0, y0;
        invers_modular(b, a%b, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
    }
}

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

    scanf("%lld%lld", &a, &n);

    invers_modular(a, n, x, y);

    if(x <= 0) x = n + x % n;
    printf("%lld\n", x);
    return 0;
}