#include <cstdio>
using namespace std;
long int A, N, D, I, R, List[500000], vflist, x, y, x0, y0, i;
int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%ld%ld", &A, &N);
    D=N; I=A; R=N%A;
    while(R){
        List[++vflist]=D/I;
        D=I;
        I=R;
        R=D%I;
    }
    List[++vflist]=D/I;
    x0=1; y0=0;
    for(i=vflist; i>=1; i--){
        x=y0;
        y=x0-List[i]*y0;
        x0=x;
        y0=y;
    }
    while(y0<0)y0+=N;
    printf("%ld", y0);

    return 0;
}