#include <stdio.h>

long long cmmdc;

void euclidExtins(long long a,long long b,long long *x,long long *y){

    if(b==0){
        cmmdc=a;
        *x=1;
        *y =0;
        return;
    }

    long long x1,y1;
    euclidExtins(b,a%b,&x1,&y1);
    *x=y1;
    *y=x1-(a/b)*y1;
}

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;
    
    euclidExtins(A,N,&x,&y);

    x=((x%N)+N)%N;

    fprintf(fout,"%lld\n",x);

    fclose(fin);
    fclose(fout);

    return 0;
}