#include <cstdio>

FILE* in;
FILE* out;

int euclid(int a, int b, int& x, int& y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }

    int d,x0,y0;

    d=euclid(b,a%b,x0,y0);

    x=y0;
    y=x0-(a/b)*y0;

    return d;
}


int a,n;

int main()
{
    in=fopen("inversmodular.in","r");
    out=fopen("inversmodular.out","w");

    fscanf(in,"%d%d",&a,&n);

    int d,rx,ry;
    d=euclid(a,n,rx,ry);

    fprintf(out,"%d",rx<0 ? rx+n : rx );


    fclose(in);
    fclose(out);
    return 0;
}