#include <cstdio>

using namespace std;

int X,MOD,Inv,Ins;

void Gcd(int A,int B,int &Inv,int &Ins)
{
    int HInv=0;

    if (!B)
    {
        Inv=1;
        Ins=0;
        return ;
    }

    Gcd(B,A%B,Inv,Ins);

    HInv=Inv;
    Inv=Ins;
    Ins=HInv-Ins*(A/B);
}

int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);

scanf("%d%d",&X,&MOD);

Gcd(X,MOD,Inv,Ins);

while (Inv<0) Inv=MOD+Inv%MOD;

printf("%d\n",Inv);

return 0;
}