//Aplicatie: Se cere (a/b)%n.
//Gasim cu Euclid extins X*b+Y*n=1
//Rezultatul este (a*(X%n))%n
#include <stdio.h>
void euclid(long long a, long long 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(){
    long long x, y, a, n;
    FILE *fin, *fout;
    fin=fopen("inversmodular.in", "r");
    fout=fopen("inversmodular.out", "w");
    fscanf(fin, "%lld%lld", &a, &n);
    x=0;
    euclid(a, n, &x, &y);
    if(x<=0){
        x=n+(x%n);
    }
    fprintf(fout, "%lld\n", x);
    fclose(fin);
    fclose(fout);
    return 0;
}