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