#include <iostream>
#include<fstream>
using namespace std;
int a,n,x[35],y[35];
void gcde(int A,int B,int lev)
{
    if(B==0)
    {
        x[lev]=1;
        y[lev]=0;
        return;
    }
    gcde(B,A%B,lev+1);
    x[lev]=y[lev+1];
    y[lev]=x[lev+1]-(A/B)*y[lev+1];
}
int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    f>>a>>n;
    gcde(a,n,1);
    if(x[1]<0)
    {
        x[1]%=n;
        x[1]+=n;
    }
    g<<x[1];
    return 0;
}