#include <cstdio>
void euclid(int a,int b,long long &x,long long &y)
{
    if(!b)
        x=1,y=0;
    else
    {
        long long x0,y0;
        euclid(b,a%b,x0,y0);
        x=y0;
        y=x0-(a/b)*y0;
    }
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("inversmodular.in","r");
    fout=fopen("inversmodular.out","w");
    int a,n;
    long long inv,y;
    fscanf(fin,"%d%d",&a,&n);
    euclid(a,n,inv,y);
    if(inv<0)
        inv+=(long long)(1-inv/n)*n;
    fprintf(fout,"%lld",inv);
    fclose(fin);
    fclose(fout);
    return 0;
}