#include <cstdio>

using namespace std;

int a,n;


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

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

   euclid(a, n, x, y);
    if (x <= 0) x = n + x % n;

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

    return 0;
}