#include<cstdio>

int gcd(int a,int b,long long int &x,long long int &y)
{
    if(!b)
    {
        x=1;
        y=0;
    }
    else
    {
        long long int temp;
        gcd(b,a%b,x,y);
        temp=x;
        x=y;
        y=temp-(a/b)*y;
    }
}

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

    int a,n;
    fscanf(fin,"%d %d",&a,&n);
    long long int inv=0,ins;

    gcd(a,n,inv,ins);

    if(inv<=0)
    {
        inv=n+inv%n;
    }

    fprintf(fout,"%lld",inv);
}