#include <cstdio>

using namespace std;

int euclid(int a, int b, int &x, int &y)
{
    if(b == 0)
        return a;
    int cmmdc = euclid(b, a%b, x, y);
    int c = a/b, x_prec = x, y_prec = y;
    x = y_prec;
    y = x_prec - c*y_prec;
    return cmmdc;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int A, N, x=1, y=0;
    scanf("%d%d",&A,&N);
    euclid(A,N,x,y);
    while(x<0)
        x+=N;
    printf("%d",x);
    return 0;
}