#include <cstdio>
using namespace std;
long long a,n,y0,y1,aux,r,c,y;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld %lld",&a,&n);
    y0=0;
    y1=1;
    aux=n;
    while (a!=0)
    {
        r=n%a;
        c=n/a;
        n=a;
        a=r;
        y=y0-c*y1;
        y0=y1;
        y1=y;
    }
    while (y0<0) y0+=aux;
    printf("%lld\n",y0);
    return 0;
}