#include <stdio.h>

void euclid_extins(int a, int b, int *x, int *y){
    if(b==0){
        *x=1;
        *y=0;
    }
    else{
        int x0, y0;
        euclid_extins(b, a%b, &x0, &y0);
        *x=y0;
        *y=x0-(a/b)*y0;
    }
}

int main()
{
    FILE *fin, *fout;
    int a, n, x, y;
    fin=fopen("inversmodular.in", "r");
    fscanf(fin, "%d%d", &a, &n);
    fclose(fin);
    euclid_extins(a, n, &x, &y);
    fout=fopen("inversmodular.out", "w");
    fprintf(fout, "%d", x+((-x)/n+1)*n%n);
    fclose(fout);
    return 0;
}