#include <cstdio>

using namespace std;

long long a, b, x, y;

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

int main()
{
    freopen ("inversmodular.in","r",stdin);
    freopen ("inversmodular.out","w",stdout);
    scanf ("%lld %lld",&a,&b);
    euclid(a,b,x,y);
    if (x<=0)
        x=b+x%b;
    printf ("%lld\n",x);
    return 0;
}