#include <cstdio>
using namespace std;
long long a,n,aux,y,y1,y0,r,c;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&a,&n);
    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;
}