#include <stdio.h>

long long sol(long long a,long long b,long long *x,long long *y) 
{
    if (b==0) 
    {
        *x=1;
        *y=0;
        return a;
    }
    long long x1,y1;
    long long g = sol(b, a % b, &x1, &y1);
    *x =y1;
    *y =x1-(a / b)*y1;
    return g;
}
int main() {
    FILE *fin=fopen("inversmodular.in","r");
    FILE *fout=fopen("inversmodular.out","w");
    long long a,n;
    fscanf(fin,"%lld %lld",&a,&n);
    long long x,y;
    sol(a,n,&x,&y);
    x=((x % n)+n)%n;
    fprintf(fout,"%lld\n",x);
    fclose(fin);
    fclose(fout);
    return 0;
}