#include<cstdio>
using namespace std;
int a,n,d,x,y;
int cmmdc(int A, int B, int &X, int &Y)
{
    int D,X0,Y0;
    if (!B)
        {
            X=1, Y=0;
            return A;
        }
    D=cmmdc(B,A%B,X0,Y0);
    X=Y0;
    Y=X0-(A/B)*Y0;
    return D;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&a,&n);
    d=cmmdc(a,n,x,y);
    printf("%d\n",x%n);
    return 0;
}