#include <cstdio>

using namespace std;

int x , mod;
long long inv , ins;

void gcd(long long &x , long long &y , int a , int b)
{
    if (!b)
        x = 1 , y = 0;
    else
    {
        gcd(x , y , b , a % b);
        long long aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}

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

    scanf("%d %d", &x, &mod);

    gcd(inv , ins , x , mod);

    if (inv <= 0) inv = mod + inv % mod;

    printf("%lld\n", inv);

    return 0;
}