#include <cstdio>

using namespace std;

int a, n;
long long x, y;

void GCD (int a, int b, long long &x, long long &y)
{
    if( !b )
    {
        x = 1;
        y = 0;
    }
    else
    {
        long long x0, y0;
        GCD(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("%d %d", &a, &n);
    GCD (a, n, x, y);

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