#include <fstream>

using namespace std;

int a,n;

void invers(int a,int b,long long &x,long long &y)
{
     if(!b)
     {
        x=1;
        y=0;
     }
     else
     {
        invers(b,a%b,x,y);
        long long aux=x;
        x=y;
        y=aux-y*(a/b);
     }
}

int main()
{
    ifstream f("inversmodular.in");
    long long x0=0,y0;
    f>>a>>n;
    invers(a,n,x0,y0);
    ofstream g("inversmodular.out");
    if (x0<=0)
       x0=n+x0%n;
    g<<x0<<endl;
    return 0;
}