#include<stdio.h>

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

    int d, xx=0, yy=0;
    d=cmmdc(b, a%b, &xx, &yy);
    *x=yy;
    *y=-((int)(a/b))*yy+xx;
    return d;
}

int main(){
    int a, n;
    freopen("inversmodular.in", "rt", stdin);
    freopen("inversmodular.out", "wt", stdout);

    scanf("%d %d", &a, &n);
    int x = 0, y = 0;
    cmmdc(a, n, &x, &y);

    while(x<0) x+=n;
    printf("%d\n", x);

    fclose(stdin);
    fclose(stdout);
    return 0;
}