#include<cstdio>
long long a,n,i,j,x,y;
FILE *f,*g;
void cmmdc(long long n,long long a,long long &x,long long &y){
    if(a==0){
        x=1;
        y=0;
        return;
    }
    long long xa,ya;
    cmmdc(a,n%a,xa,ya);
    x=ya;
    y=xa-(n/a)*ya;
}
int main(){
    f=fopen("inversmodular.in","r");
    g=fopen("inversmodular.out","w");
    fscanf(f,"%lld%lld",&a,&n);
    cmmdc(n,a,x,y);
    if(y<0)
        y=( ( y + ( - y ) / n + 1 ) * n ) % n;
    fprintf(g,"%lld",y);
    fclose(f);
    fclose(g);
    return 0;
}