#include <fstream>

using namespace std;

long long inv,ins,n,a;
void gcd(long long &x,long long &y, int a,int b)
{
    long long aux;
    if (!b)
         x = 1, y = 0;
     else
     {
         gcd(x,y,b,a%b);
         aux=x;
         x=y;
         y=aux - y * (a / b);
     }
}
int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    f>>a>>n;
    gcd(inv,ins,a,n);
    if (inv <= 0)
       inv=n+inv%n;
    g<<inv<<'\n';
    f.close();
    g.close();
    return 0;
}